算法笔记+个人代码(菜,仅供参考)
笔记未完成,正在更新
已完成:数组、排序、链表、哈希表、栈和队列、二叉树、回溯、贪心、动态规划
正在更新:图论、字符串、单调栈
版本:2023-08-31
题目参考:https://www.programmercarl.com/
Algorithm-learning-notes基础算法总结数组1:二分查找数组3:有序数组的平方数组4:长度最小的子数组|滑动窗口排序专题:1插入排序数组的插入排序排序插入排序优化:折半插入排序链表的插入排序2希尔排序3冒泡排序数组的冒泡排序链表的冒泡排序4快速排序5选择排序数组的选择排序:链表的选择排序6堆排序无脑递归版本:(空间复杂度偏高)奇妙循环版本:复杂度分析:(对于循环版本的代码)应用:合并K个升序链表7归并排序复杂度分析对数组归并排序对链表归并排序8基数排序复杂度分析对链表基数排序链表1:移除链表元素链表2:设计链表链表3:反转链表链表4:两两交换链表中的节点链表5:删除链表的倒数第N个节点链表6:相交链表链表7:环形链表II*哈希表1: 有效的字母异位词哈希表2:两个数组的交集哈希表3:快乐数哈希表4:两数之和哈希表5:四数相加II哈希表6:赎金信哈希表6.9:两数之和 II - 输入有序数组哈希表7:三数之和字符串1:反转字符串字符串2:反转字符串II字符串3:替换空格字符串4:反转字符串中的单词字符串6:找出字符串中第一个匹配项的下标字符串7:重复的子字符串字符串8:有效数字方法1:暴力if-else方法2:有限状态自动机方法3:正则表达式字符串9:验证IP地址字符串10:实现Trie(前缀树)字符串11:连接词字符串12:字符流栈和队列4:有效的括号栈和队列5:删除字符串中的所有相邻重复项栈和队列6:逆波兰表达式求值栈和队列7:基本计算器栈和队列8:基本计算器II二叉树2.递归遍历二叉树3.非递归遍历先序遍历:后序遍历:中序遍历:*二叉树5:层序遍历二叉树6:翻转二叉树二叉树8:对称二叉树二叉树9:二叉树的最大深度二叉树10:二叉树的最小深度二叉树11:完全二叉树的节点个数方法1:二分查找+位运算方法2:寻找满二叉树二叉树12:平衡二叉树二叉树13:二叉树的所有路径二叉树15:左叶子之和二叉树16:找树左下角的值二叉树17:路径总和二叉树18:从中序与后序遍历序列构造二叉树, 从前序与中序遍历序列构造二叉树二叉树19:最大二叉树二叉树21:合并二叉树二叉树22:二叉搜索树中的搜索二叉树23:验证二叉搜索树二叉树24:二叉搜索树的最小绝对差二叉树25:二叉搜索树中的众数二叉树26:二叉树的最近公共祖先二叉树28:二叉搜索树的最近公共祖先二叉树29:二叉搜索树的插入操作二叉树30:删除二叉搜索树中的节点回溯2:组合回溯4:组合总和III回溯5:电话号码的字母组合回溯7:组合总和回溯8:组合总和II回溯9:分割回文串回溯10:复原IP地址回溯11:子集回溯13:子集II回溯14:递增子序列回溯15:全排列回溯16:全排列II回溯19:重新安排行程回溯20:N皇后回溯21:解数独贪心2:分发饼干贪心3:摆动序列贪心4:最大子数组和贪心6:买卖股票的最佳时机 II贪心7:跳跃游戏贪心8:跳跃游戏II贪心9:K次取反后最大化的数组和贪心11: 加油站贪心12:分发糖果贪心13:柠檬水找零贪心14:根据身高重建队列*贪心17:用最少数量的箭引爆气球*贪心18:无重叠区间贪心19:划分字母区间贪心20:合并区间贪心22:单调递增的数字贪心23:监控二叉树图论最小生成树:连接所有节点的最小费用prim普里姆算法Kruskal算法最短路径问题:Dijkstra算法Dijkstra算法优化:使用小根堆priority_queueFloyd算法Bellman-ford算法SPFA算法拓扑排序课程表课程表II图论1:统计点对的数目代码随想录的刷题顺序:动态规划3:爬楼梯动态规划4:使用最小花费爬楼梯动态规划6:不同路径动态规划7:不同路径II动态规划8:整数拆分动态规划9:不同的二叉搜索树0-1背包系列 13~17动态规划13:分割等和子集动态规划14:最后一块石头的重量II动态规划16:目标和动态规划17:一和零完全背包系列 19~26动态规划19:零钱兑换II动态规划21:组合总和IV动态规划23:零钱兑换动态规划24:完全平方数动态规划26:单词拆分打家劫舍问题29-31动态规划29:打家劫舍动态规划30:打家劫舍II动态规划31:打家劫舍III股票问题32-38动态规划32.买卖股票的最佳时机动态规划34.买卖股票的最佳时机II动态规划35.买卖股票的最佳时机III动态规划36:买卖股票的最佳时机IV动态规划37:买卖股票的最佳时机含冷冻期动态规划38:买卖股票的最佳时机含手续费子序列问题动态规划41:最长递增子序列动态规划42:最长连续递增序列动态规划43:最长公共子序列动态规划44:最长公共子序列动态规划45:不相交的线动态规划46:最大子序和动态规划47:判断子序列动态规划48:不同的子序列动态规划49:两个字符串的删除操作动态规划50:编辑距离动态规划52:回文子串动态规划53:最长回文子序列动态规划54:切披萨的方案数灵神的刷题顺序:动态规划:从记忆化搜索到递推198打家劫舍70. 爬楼梯746. 使用最小花费爬楼梯2466.统计构造好字符串的方案数213.打家劫舍 II拆分类动态规划343.整数拆分96.不同的二叉搜索树0-1背包和完全背包494. 目标和(0-1背包)解法1. 回溯(暴力)解法:可以1952ms踩线通过解法2:灵神的0-1背包记忆递归模板记忆递归模板解题解法3: 数组递推的动态规划解法322. 零钱兑换416. 分割等和子集1049.最后一块石头的重量II279. 完全平方数518. 零钱兑换 II377.组合总和IV474. 一和零879.盈利计划最长公共子序列1143.最长公共子序列72. 编辑距离583. 两个字符串的删除操作712. 两个字符串的最小ASCII删除和1458. 两个子序列的最大点积97. 交错字符串单调栈1:每日温度单调栈2:下一个更大元素I
手把手带你撕出正确的二分法 | 二分查找法 | 二分搜索法 | LeetCode:704. 二分查找(参考视频)
左闭右闭模板:
注意四个细节:
right=len-1left<=rightright=mid-1left=mid+1C++
1class Solution {2public:3 int search(vector<int>& nums, int target) 4 {5 int len=nums.size();6 int left=0;7 int right=len-1;8 while(left<=right)//左闭右闭9 {10 int mid=(left+right)/2;11 if(nums[mid]==target)12 return mid;13 else if(nums[mid]>target)14 right=mid-1;15 else 16 left=mid+1;17 }18 return -1;19 }20};python:
xxxxxxxxxx131class Solution:2 def search(self, nums: List[int], target: int) -> int:3 left=04 right=len(nums)-15 while left<=right: # 左闭右闭6 mid=(left+right)//27 if nums[mid]==target:8 return mid9 elif nums[mid]>target:10 right=mid-111 else:12 left=mid+113 return -1左闭右开模板:
注意四个细节:
right=nums.size()left<rightleft=mid+1right=midC++:
xxxxxxxxxx191class Solution {2public:3 int search(vector<int>& nums, int target) 4 {5 int left=0;6 int right=nums.size();7 while(left<right) //左闭右开8 {9 int mid=(left+right)/2;10 if(nums[mid]==target)11 return mid;12 else if(nums[mid]<target)13 left=mid+1;14 else15 right=mid;16 }17 return -1;18 }19};python:
x1class Solution:2 def search(self, nums: List[int], target: int) -> int:3 left=04 right=len(nums)5 while left<right: # 左闭右开6 mid=(left+right)//27 if nums[mid]==target:8 return mid9 elif nums[mid]<target:10 left=mid+111 else:12 right=mid13 return -114
双指针法经典题目 | LeetCode:977.有序数组的平方(参考视频)
推荐双指针法,由绝对值最小的数开始往两边遍历
当然也可以由两边向中间遍历数组
python:
xxxxxxxxxx271class Solution:2 def sortedSquares(self, nums: List[int]) -> List[int]:3 le=len(nums)4 idx=05 for idx in range(le):6 if idx+1<le and abs(nums[idx+1])>abs(nums[idx]):7 break8 left=idx-19 right=idx+110 arr=[nums[idx]**2]11 while 1:12 if left>=0 and right<le:13 if abs(nums[left])<abs(nums[right]):14 arr.append(nums[left]**2)15 left-=116 else: 17 arr.append(nums[right]**2)18 right+=119 elif left>=0:20 arr.append(nums[left]**2)21 left-=122 elif right<le:23 arr.append(nums[right]**2)24 right+=125 else:26 break27 return arr拿下滑动窗口! | LeetCode 209 长度最小的子数(参考视频)
python:
xxxxxxxxxx211class Solution:2 def minSubArrayLen(self, target: int, nums: List[int]) -> int:3 le=len(nums)4 left=add=05 right=-16 ret=inf7 while right+1<le:8 while add<=target and right+1<le:9 right+=110 add+=nums[right]11 if add>=target:12 ret=min(ret,right-left+1)13 while add>target:14 add-=nums[left]15 left+=116 if add>=target:17 ret=min(ret,right-left+1)18 if ret==inf:19 return 020 else :21 return ret数组排序:leetcode912
单链表排序:leetcode148(测试用例很容易超时,matrix的面试题,当年我就没做出来😖)
对链表进行插入排序:leetcode147(不容易超时)

支持数组和链表
空间复杂度
最好时间复杂度:
最坏时间复杂度:
平均时间复杂度:
具有稳定性
xxxxxxxxxx191class Solution {2public:3 vector<int> sortArray(vector<int>& nums) //插入排序4 {5 int n=nums.size();//数组长度6 for(int i=1;i<n;++i)7 {8 if(nums[i-1]>nums[i])9 {10 int tmp=nums[i];//取出当前遍历的元素11 int j=i-1;12 for(;j>=0&&nums[j]>tmp;--j)//向左遍历,直到遍历到小于或等于tmp的元素13 nums[j+1]=nums[j];//将比tmp大的元素右移一格14 nums[j+1]=tmp;//将tmp插入新的位置15 }16 }17 return nums;18 }19};(在leetcode912提交会超时.leetcode147通过)
当遍历到第i个1元素时,[0,i-1]的所有元素时有序的,可以利用二分查找的方法找到插入位置
然鹅, 时间复杂度没有质的飞跃
空间复杂度
最好时间复杂度:
最坏时间复杂度:
平均时间复杂度:
具有稳定性
xxxxxxxxxx281class Solution {2public:3 vector<int> sortArray(vector<int>& nums) //插入排序4 {5 int n=nums.size();//数组长度6 for(int i=1;i<n;++i)7 {8 if(nums[i-1]>nums[i])9 {10 int left=0,right=i-1;11 while(left<=right)//二分查找12 {13 int mid=(left+right)/2;14 if(nums[i]>=nums[mid])//这里取等是为了算法的稳定性15 left=mid+1;16 else 17 right=mid-1;18 }19 //将[left,i-1]的所有元素右移20 int tmp=nums[i];21 for(int j=i-1;j>=left;--j)22 nums[j+1]=nums[j];23 nums[left]=tmp;24 }25 }26 return nums;27 }28};(在leetcode912提交会超时)
空间复杂度:
最好时间复杂度:
最坏时间复杂度:
平均时间复杂度:
具有稳定性
xxxxxxxxxx281class Solution {//插入排序2public:3 ListNode* sortList(ListNode* head) 4 {5 if(head==nullptr)//保证链表长度≥16 return head;7 ListNode* dummyhead=new ListNode(0,head);8 ListNode* i=head;9 while(i->next!=nullptr)10 {11 if(i->val>i->next->val)12 {13 ListNode* tmp=i->next;//取出当前节点14 i->next=tmp->next;//将当前节点从链表删除15 ListNode* j=dummyhead;16 while(j->next->val<=tmp->val)17 j=j->next;18 tmp->next=j->next;19 j->next=tmp;//将当前tmp节点插入链表20 }21 else22 i=i->next;23 }24 ListNode* ret=dummyhead->next;25 delete dummyhead;26 return ret;27 }28};(在leetcode148提交会超时,leetcode147提交通过,16ms,9.3MB)
仅支持数组,不适用链表
先追求表中元素部分有序,再逐渐逼近全局有序
每一轮都按照一个给定的间隔进行插入排序,这个间隔应当逐渐减少,最后必须为1
以下的代码中, 步长(间隔)从
空间复杂度:
时间复杂度:和增量序列
最坏时间复杂度
当
不具有稳定性,例如:
原始序列: 65 49 49
第一趟:d=2 49 49 65
第一趟:d=1 49 49 65
xxxxxxxxxx221class Solution {2public:3 vector<int> sortArray(vector<int>& nums) //希尔排序4 {5 int n=nums.size();//数组长度6 for(int d=n/2;d>=1;d/=2)//步长变化7 {8 for(int i=d;i<n;++i)9 {10 if(nums[i-d]>nums[i])11 {12 int tmp=nums[i];13 int j=i-d;14 for(;j>=0&&nums[j]>tmp;j-=d)15 nums[j+d]=nums[j];16 nums[j+d]=tmp;17 }18 }19 }20 return nums;21 }22};(在leetcode912提交通过,224ms,65MB)
可用于数组和链表
空间复杂度:
时间复杂度
最好情况(有序):
最坏情况(逆序):
平均时间复杂度:
具有稳定性
xxxxxxxxxx231class Solution {2public:3 vector<int> sortArray(vector<int>& nums) //冒泡排序4 {5 int n=nums.size();//数组长度6 //每一轮都把最小的元素移动到前面7 for(int i=0;i<n-1;++i)8 {9 int flag=0;//本趟冒泡是否发生交换的标志10 for(int j=n-2;j>=i;--j)//一趟冒泡11 {12 if(nums[j]>nums[j+1])//如果逆序13 {14 flag=1;15 swap(nums[j],nums[j+1]);//交换16 }17 }18 if(flag==0)//本趟遍历没有交换,当前数组已经有序,不需要继续循环19 break;20 }21 return nums;22 }23};(在leetcode912提交会超时)
xxxxxxxxxx4112class Solution {//冒泡排序3public:4 ListNode* sortList(ListNode* head) 5 {6 if(head==nullptr||head->next==nullptr)//保证链表长度>17 return head;8 ListNode* dummyhead=new ListNode(0,head);//虚拟头节点9 int cur_max=INT_MAX;10 ListNode* pre=dummyhead,*left=head,*right=head->next;11 while(right!=nullptr&&right->val<=cur_max)12 {13 int flag=0;14 while(right!=nullptr&&right->val<=cur_max)15 {16 if(left->val>right->val)17 {18 left->next=right->next;19 right->next=left;20 pre->next=right;21 pre=right;22 right=left->next;23 flag=1;24 }25 else26 {27 pre=left;28 left=right;29 right=right->next;30 }31 }32 cur_max=left->val;33 pre=dummyhead,left=dummyhead->next,right=left->next;34 if(flag==0)35 break;36 }37 ListNode* ret=dummyhead->next;38 delete dummyhead;39 return ret;40 }41};(在leetcode148提交会超时,leetcode147通过112ms,9.3MB)
最好空间复杂度:
最坏空间复杂度:
最好时间复杂度:
最坏时间复杂度:
平均时间复杂度
如果每次选中的枢轴将待排序序列划分为均匀的两个部分,则递归深度最小,算法效率最高
若数组原本就有序或逆序,则快速排序性能最差
算法不稳定
xxxxxxxxxx281class Solution {2public:3 vector<int> sortArray(vector<int>& nums)//快速排序4 {5 int n=nums.size();6 function<void(int,int)>quick_sort=[&](int low,int high)7 {8 if(low>=high)9 return;10 int left=low,right=high;11 int pivot=nums[low];12 while(low<high)13 {14 while(low<high&&nums[high]>=pivot)15 --high;16 nums[low]=nums[high];17 while(low<high&&nums[low]<=pivot)18 ++low;19 nums[high]=nums[low];20 }21 nums[low]=pivot;22 quick_sort(left,low-1);23 quick_sort(low+1,right);24 };25 quick_sort(0,n-1);26 return nums;27 }28};(在leetcode912提交会超时)
空间复杂度
时间复杂度
不稳定,例如:主要原因是使用了swap函数,如果牺牲一些时间,整体后移所有元素以避免使用swap,算法可以变为稳定的
原始序列 3 3 1
排序后 1 3 3
xxxxxxxxxx221class Solution {2public:3 vector<int> sortArray(vector<int>& nums)//快速排序4 {5 int n=nums.size();6 for(int i=0;i<n-1;++i)7 {8 int cur_min=INT_MAX;9 int min_idx=i;10 for(int j=i;j<n;++j)11 {12 if(nums[j]<cur_min)13 {14 cur_min=nums[j];15 min_idx=j;16 }17 }18 swap(nums[i],nums[min_idx]);19 }20 return nums;21 }22};(在leetcode912提交会超时)
空间复杂度
时间复杂度
具有稳定性
xxxxxxxxxx361class Solution {2public:3 ListNode* sortList(ListNode* head) //选择排序4 {5 ListNode* dummyhead=new ListNode(0,head);//虚拟头节点6 ListNode* i=dummyhead,*j=dummyhead;7 while(i->next!=nullptr)8 {9 j=i;10 int cur_min=INT_MAX;11 ListNode* min_node=i;12 while(j->next!=nullptr)13 {14 if(j->next->val<cur_min)15 {16 cur_min=j->next->val;17 min_node=j;18 }19 j=j->next;20 }21 if(min_node==i)22 i=i->next;23 else24 {25 ListNode* tmp=min_node->next;26 min_node->next=tmp->next;27 tmp->next=i->next;28 i->next=tmp;29 i=tmp;30 }31 }32 ListNode* ret=dummyhead->next;33 delete dummyhead;34 return ret;35 }36};(在leetcode148提交会超时,leetcode147通过,80ms,9.4MB)
只适用于数组
堆排序利用大根堆,本质是按照节点序号(从1开始)存储在数组中的完全二叉树
几个基本操作
若完全二叉树中有n个节点,则
若n个关键字序列
如果下标从0开始,则:
xxxxxxxxxx481class Solution {2public:3 vector<int> sortArray(vector<int>& nums)//堆排序4 {5 int n=nums.size();6 function<void(int)>recur=[&](int idx)7 {8 if(2*idx+1>=n)//没有子树9 return;10 else if(2*idx+2>=n)//只有左子树11 {12 if(nums[2*idx+1]>nums[idx])13 {14 swap(nums[2*idx+1],nums[idx]);15 recur(2*idx+1);16 }17 }18 else//有左右子树19 {20 if(nums[2*idx+1]>nums[2*idx+2])//左子树更大21 {22 if(nums[2*idx+1]>nums[idx])23 {24 swap(nums[2*idx+1],nums[idx]);25 recur(2*idx+1);26 }27 }28 else//右子树更大29 {30 if(nums[2*idx+2]>nums[idx])31 {32 swap(nums[2*idx+2],nums[idx]);33 recur(2*idx+2);34 }35 }36 }37 };38 for(int i=n/2-1;i>=0;--i)//构造大根堆39 recur(i);40 while(n>=2)41 {42 --n;43 swap(nums[n],nums[0]);44 recur(0);45 }46 return nums;47 }48};leetcode912通过,308ms,65MB
xxxxxxxxxx291class Solution {2public:3 vector<int> sortArray(vector<int>& nums)//堆排序(非递归版本)4 {5 int n=nums.size();6 function<void(int,int)>head_adjust=[&](int idx,int len)7 {8 int k=2*idx+1;//idx对应的左孩子的下标9 while(k<len)//idx的左孩子存在10 {11 if(k+1<len&&nums[k]<nums[k+1])//idx的右孩子存在且值大于左孩子12 ++k;//调整k,保证k指向左右孩子中的最大者13 if(nums[idx]>=nums[k])14 break;//idx节点最大,结束循环15 swap(nums[idx],nums[k]);16 idx=k;//以当前孩子为父节点,继续向下检查17 k=2*idx+1;//指向当前孩子的左孩子的下标 18 }19 };20 for(int i=n/2-1;i>=0;--i)//构造大根堆21 head_adjust(i,n);22 for(int i=n-1;i>=1;--i)23 {24 swap(nums[0],nums[i]);25 head_adjust(0,i);26 }27 return nums;28 }29};leetcode912通过,204ms,65MB
复杂度分析部分考虑下标从1开始
二叉树高
第
把整棵树调整为大根堆, 关键字对比次数:
所以建堆的过程中时间复杂度
排序的过程中总共需要处理n-1个节点,每个节点最多需要下坠h-1层,时间复杂度
总的时间复杂度
空间复杂度
堆排序不稳定,例如
原始序列 1 2 2
排序后 1 2 2
利用小根堆的性质解决
C++:
xxxxxxxxxx6012class Solution {3public:4 ListNode* mergeKLists(vector<ListNode*>& lists) 5 {6 ListNode* dummyhead=new ListNode(0,nullptr);//虚拟头节点7 ListNode* p=dummyhead;8 int n=lists.size();9 if(n==0)10 return nullptr;11 //将lists构造为一个小根堆(按照链表中第一个元素的大小排序)12 function<void(int)>recur=[&](int idx)13 {14 if(idx>n/2-1)//没有孩子15 return;16 int fa,le,ri;//分别是父节点、左节点、右节点,得到它们的权值用于排序17 if(lists[idx]==nullptr)18 fa=ninf;19 else20 fa=lists[idx]->val;21 if(2*idx+1>=n||lists[2*idx+1]==nullptr)22 le=ninf;23 else24 le=lists[2*idx+1]->val;25 if(2*idx+2>=n||lists[2*idx+2]==nullptr)26 ri=ninf;27 else28 ri=lists[2*idx+2]->val;29 if(le<ri)30 {31 if(le<fa)32 {33 swap(lists[2*idx+1],lists[idx]);34 recur(2*idx+1);35 }36 }37 else38 {39 if(ri<fa)40 {41 swap(lists[2*idx+2],lists[idx]);42 recur(2*idx+2);43 }44 }45 };//用于构造和维护小根堆的递归函数46 for(int i=n/2-1;i>=0;--i)47 recur(i);48 while(lists[0]!=nullptr)49 {50 p->next=lists[0];51 p=p->next;52 lists[0]=p->next;53 p->next=nullptr;54 recur(0);55 }56 ListNode* ret=dummyhead->next;57 delete dummyhead;58 return ret;59 }60};2路归并的归并树,形态上就是一棵倒立的二叉树
二叉树的第h层最多有
即
n个元素进行二路归并排序,归并趟数=
每趟归并的时间复杂度
递归工作栈的空间复杂度为
总的空间复杂度
归并排序具有稳定性
xxxxxxxxxx391class Solution {2public:3 vector<int> sortArray(vector<int>& nums)//归并排序4 {5 int n=nums.size();6 vector<int>tmp(n);7 function<void(int,int)>merge_sort=[&](int left,int right)8 {9 if(left>=right)10 return;11 int mid=(left+right)/2;12 merge_sort(left,mid);13 merge_sort(mid+1,right);14 for(int i=left;i<=right;++i)//将[left,right]的元素临时移动到tmp数组15 tmp[i]=nums[i];16 int i=left,j=mid+1,k=left;17 while(i<=mid&&j<=right)18 {19 if(tmp[i]<=tmp[j])20 {21 nums[k]=tmp[i];22 ++i;23 }24 else25 {26 nums[k]=tmp[j];27 ++j;28 }29 ++k;30 }31 for(;i<=mid;++i,++k)32 nums[k]=tmp[i];33 for(;j<=right;++j,++k)34 nums[k]=tmp[j];35 };36 merge_sort(0,n-1);37 return nums;38 }39};leetcode912通过,312ms,67.1MB
xxxxxxxxxx721class Solution {2public:3 ListNode* sortList(ListNode* head) 4 {5 ListNode* dummyhead=new ListNode(0,head);//虚拟头节点6 function<void(ListNode*,ListNode*&)>merge_sort=[&](ListNode* left,ListNode*& right)//左开右闭区间7 {8 if(left==right||left->next==right)9 return;10 ListNode* mid=left, * fast=left;//采用快慢指针法找到链表的中点11 while(fast->next!=right)12 {13 fast=fast->next;14 mid=mid->next;15 if(fast->next==right)16 break;17 fast=fast->next;18 }19 merge_sort(left,mid);20 merge_sort(mid,right);21 ListNode* ld=new ListNode(0,left->next),*rd=new ListNode(0,mid->next),*end=right->next;22 ListNode* p=left;23 mid->next=nullptr;24 right->next=nullptr;25 left->next=end;26 while(ld->next!=nullptr&&rd->next!=nullptr)27 {28 ListNode* tmp;29 if(ld->next->val<=rd->next->val)30 {31 tmp=ld->next;32 ld->next=tmp->next;33 }34 else35 {36 tmp=rd->next;37 rd->next=tmp->next;38 }39 tmp->next=p->next;40 p->next=tmp;41 p=tmp;42 }43 while(ld->next!=nullptr)44 {45 ListNode* tmp;46 tmp=ld->next;47 ld->next=tmp->next;48 tmp->next=p->next;49 p->next=tmp;50 p=tmp;51 }52 while(rd->next!=nullptr)53 {54 ListNode* tmp;55 tmp=rd->next;56 rd->next=tmp->next;57 tmp->next=p->next;58 p->next=tmp;59 p=tmp;60 }61 right=p;62 delete ld,rd;63 };64 ListNode* p=dummyhead;65 while(p->next!=nullptr)66 p=p->next;67 merge_sort(dummyhead,p);68 ListNode* ret=dummyhead->next;69 delete dummyhead;70 return ret;71 }72};leetcode148通过,368ms,95.18MB
通常针对链表实现,假设长度为n的线性表中每个节点
其中,
空间复杂度
一趟分配
对于leetcode148,
排序时加上
所有该题时间复杂度
基数排序是稳定的, 因为基你太稳
xxxxxxxxxx471class Solution {2public:3 ListNode* sortList(ListNode* head)//基数排序4 {5 ListNode* dummyhead=new ListNode(0,head);6 ListNode* p=dummyhead;7 while(p->next!=nullptr)8 {9 p->next->val+=100000;10 p=p->next;11 }12 vector<queue<ListNode*>>vec(10);13 for(int i=1;i<=100000;i*=10)14 {15 int flag=0;16 while(dummyhead->next!=nullptr)17 {18 if(dummyhead->next->val/(i*10)!=0)19 flag=1;20 vec[dummyhead->next->val/i%10].push(dummyhead->next);21 dummyhead->next=dummyhead->next->next;22 }23 ListNode* p=dummyhead;24 for(int j=0;j<10;++j)25 {26 while(!vec[j].empty())27 {28 vec[j].front()->next=p->next;29 p->next=vec[j].front();30 p=p->next;31 vec[j].pop();32 }33 }34 if(flag==0)35 break;36 }37 p=dummyhead;38 while(p->next!=nullptr)39 {40 p->next->val-=100000;41 p=p->next;42 }43 ListNode* ret=dummyhead->next;44 delete dummyhead;45 return ret;46 }47};leetcode148通过,216ms,63.4MB
使用虚拟头节点:
C++
xxxxxxxxxx361/**2 * Definition for singly-linked list.3 * struct ListNode {4 * int val;5 * ListNode *next;6 * ListNode() : val(0), next(nullptr) {}7 * ListNode(int x) : val(x), next(nullptr) {}8 * ListNode(int x, ListNode *next) : val(x), next(next) {}9 * };10 */11class Solution {12public:13 ListNode* removeElements(ListNode* head, int val)14 {15 ListNode* dummyhead=new ListNode(-1,head);16 ListNode* pre=dummyhead;17 ListNode* cur=head;18 while(cur!=nullptr)19 {20 if(cur->val==val)21 {22 pre->next=cur->next;23 delete cur;24 cur=pre->next;25 }26 else27 {28 pre=pre->next;29 cur=cur->next;30 }31 }32 head=dummyhead->next;33 delete dummyhead;34 return head;35 }36};不使用虚拟头节点:
python
xxxxxxxxxx161# Definition for singly-linked list.2# class ListNode:3# def __init__(self, val=0, next=None):4# self.val = val5# self.next = next6class Solution:7 def removeElements(self, head: Optional[ListNode], val: int) -> Optional[ListNode]:8 while head!=None and head.val==val:9 head=head.next10 p=head11 while p!=None and p.next!=None:12 if p.next.val==val:13 p.next=p.next.next14 else:15 p=p.next16 return head单向链表(使用虚拟头节点):
xxxxxxxxxx921// struct ListNode 2// {3// int val;4// ListNode *next;5// ListNode() : val(0), next(nullptr) {}6// ListNode(int x) : val(x), next(nullptr) {}7// ListNode(int x, ListNode *next) : val(x), next(next) {}8// };9class MyLinkedList {10public:11 ListNode* root;12 MyLinkedList() 13 {14 root=new ListNode;15 } 16 int get(int index) 17 {18 if(index<0)19 return -1;20 ListNode* p=root;21 int i=-1;22 while(i<index&&p->next!=nullptr)23 {24 p=p->next;25 ++i;26 }27 if(i<index)28 return -1;29 else30 return p->val;31 }32 33 void addAtHead(int val) 34 {35 ListNode* add=new ListNode(val,root->next);36 root->next=add;37 }38 39 void addAtTail(int val) 40 {41 ListNode* p=root;42 while(p->next!=nullptr)43 p=p->next;44 p->next=new ListNode(val);45 }46 47 void addAtIndex(int index, int val) 48 {49 if(index<0)50 return;51 --index;52 ListNode* p=root;53 int i=-1;54 while(i<index&&p->next!=nullptr)55 {56 p=p->next;57 ++i;58 }59 if(i<index)60 return;61 else62 {63 ListNode* add=new ListNode(val,p->next);64 p->next=add;65 }66 }67 void deleteAtIndex(int index) 68 {69 if(index<0)70 return;71 --index;72 ListNode* p=root;73 int i=-1;74 while(i<index&&p->next!=nullptr)75 {76 p=p->next;77 ++i;78 }79 if(i<index)80 return;81 else82 {83 if(p->next!=nullptr)84 {85 ListNode* rubbish=p->next;86 p->next=p->next->next;87 delete rubbish;88 }89 }90
91 }92};方法1:栈
时间复杂度
xxxxxxxxxx251class Solution {2public:3 ListNode* reverseList(ListNode* head) 4 {5 if(head==nullptr)6 return head;7 stack<ListNode*>sta;8 while(head!=nullptr)9 {10 sta.push(head);11 head=head->next;12 }13 head=sta.top();14 sta.pop();15 ListNode* p=head;16 while(!sta.empty())17 {18 p->next=sta.top();19 p=p->next;20 sta.pop();21 }22 p->next=nullptr;23 return head;24 }25};方法2:双指针
时间复杂度
xxxxxxxxxx151class Solution {2public:3 ListNode* reverseList(ListNode* head) 4 {5 ListNode* pre=nullptr,*cur=head;6 while(cur!=nullptr)7 {8 ListNode* tmp=cur->next;9 cur->next=pre;10 pre=cur;11 cur=tmp;12 }13 return pre;14 }15};方法3:递归
时间复杂度
xxxxxxxxxx161class Solution {2public:3 ListNode* reverseList(ListNode* head) 4 {5 ListNode* pre=nullptr,*cur=head;6 function<ListNode*(ListNode*,ListNode*)>recursion=[&](ListNode* cur,ListNode* pre)7 {8 if(cur==nullptr) 9 return pre;10 ListNode* tmp=cur->next;11 cur->next=pre;12 return recursion(tmp,cur);13 };14 return recursion(head,nullptr);15 }16};xxxxxxxxxx261class Solution {2public:3 ListNode* swapPairs(ListNode* head) 4 {5 if(head==nullptr||head->next==nullptr)6 return head;7 ListNode* dummyhead=new ListNode(-1,head);8 ListNode* pre=dummyhead;9 ListNode* first=head;10 ListNode* second=head->next;11 while(1)12 {13 first->next=second->next;14 second->next=first;15 pre->next=second;16 pre=first;17 first=pre->next;18 if(first==nullptr||first->next==nullptr)19 break;20 second=first->next;21 }22 first=dummyhead->next;23 delete dummyhead;24 return first;25 }26};快慢指针法:先将右指针右移n个节点,再将左右指针一起右移,直到右指针的下一个位置为nullptr,此时左指针指向待删除节点的上一个位置
xxxxxxxxxx211class Solution {2public:3 ListNode* removeNthFromEnd(ListNode* head, int n) 4 {5 ListNode* dummyhead=new ListNode(-1,head);6 ListNode* left=dummyhead,*right=dummyhead;7 for(int i=0;i<n;++i)8 right=right->next;9 while(right->next!=nullptr)10 {11 right=right->next;12 left=left->next;13 }14 ListNode* rubbish=left->next;15 left->next=left->next->next;16 delete rubbish;17 ListNode* ret=dummyhead->next;18 delete dummyhead;19 return ret;20 }21};xxxxxxxxxx501class Solution {2public:3 ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) 4 {5 ListNode* p=headA;6 int alen=1,blen=1;7 while(p->next!=nullptr)8 {9 p=p->next;10 ++alen;11 }12 p=headB;13 while(p->next!=nullptr)14 {15 p=p->next;16 ++blen;17 }18 ListNode* p1;19 if(alen>blen)20 {21 p=headA;22 for(int i=0;i<alen-blen;++i)23 {24 p=p->next;25 if(p==headB)26 return headB;27 }28 p1=headB;29 }30 else31 {32 p=headB;33 for(int i=0;i<blen-alen;++i)34 {35 p=p->next;36 if(p==headA)37 return headA;38 }39 p1=headA;40 }41 while(p!=nullptr&&p1!=nullptr)42 {43 if(p==p1)44 return p;45 p=p->next;46 p1=p1->next;47 }48 return nullptr;49 }50};xxxxxxxxxx51[--------a-------][---------b--------]2_____________________________________ <--快慢指针在这里相遇3|___________________|4[----------c--------]5
快慢指针法:
快指针一次移动2个节点,慢指针一次移动1个节点,移动完成后才检查二者是否相遇,两者相对速度1个节点,所以不会存在快指针越过慢指针而没有检测到的情况
对于慢指针 t=a+b
可以证明慢指针在圈里的路程不足一圈,不是t=a+b+k(b+c), 因为慢指针进入圈内时,快指针已经在圈内,慢指针要转完一圈,快指针就会转两圈,所以在慢指针转完一圈之前,快指针就会和慢指针相遇
对于快指针 2t=a+b+n(b+c)
所以a=(n-1)(b+c)+c
让两个指针分别从头节点和相遇点出发,二者一定会在环的入口处相遇
时间复杂度
C++:
xxxxxxxxxx261class Solution {2public:3 ListNode *detectCycle(ListNode *head) 4 {5 ListNode* fast=head,*slow=head;6 while(1)7 {8 if(fast==nullptr||slow==nullptr)9 return nullptr;10 fast=fast->next;11 if(fast==nullptr)12 return nullptr;13 fast=fast->next;14 slow=slow->next;15 if(fast==slow)16 break;17 }18 ListNode* p=head;19 while(p!=fast)20 {21 p=p->next;22 fast=fast->next;23 }24 return p;25 }26};python:
xxxxxxxxxx191class Solution:2 def detectCycle(self, head: Optional[ListNode]) -> Optional[ListNode]:3 fast=head4 slow=head5 while 1:6 if fast==None or slow==None:7 return None8 fast=fast.next9 if fast==None:10 return None11 fast=fast.next12 slow=slow.next13 if fast==slow:14 break15 p=head16 while p!=fast:17 p=p.next18 fast=fast.next19 return p简单题,大佬们可以直接跳过
用数组代替哈希表
xxxxxxxxxx151class Solution {2public:3 bool isAnagram(string s, string t) 4 {5 vector<int>vec(26);6 for(char& ch:s)7 ++vec[ch-'a'];8 for(char& ch:t)9 --vec[ch-'a'];10 for(int& n:vec)11 if(n!=0)12 return false;13 return true;14 }15};简单题,大佬们可以直接跳过
python:
xxxxxxxxxx111class Solution:2 def intersection(self, nums1: List[int], nums2: List[int]) -> List[int]:3 hash=dict()4 for n in nums1:5 hash[n]=16 ret=[]7 for n in nums2:8 if n in hash and hash[n]==1:9 ret.append(n)10 hash[n]=011 return retxxxxxxxxxx241using ll=long long;2class Solution {3public:4 bool isHappy(int n) 5 {6 unordered_map<ll,int>hash;7 while(n!=1)8 {9 if(hash[n]==1)10 return false;11 else 12 hash[n]=1;13 ll num=0;14 while(n!=0)15 {16 ll tmp=n%10;17 num+=tmp*tmp;18 n/=10;19 }20 n=num;21 }22 return true;23 }24};经典好题
C++:
xxxxxxxxxx171class Solution {2public:3 vector<int> twoSum(vector<int>& nums, int target) 4 {5 unordered_map<int,int> hash;6 int i=1;7 for(auto num:nums)8 {9 if(hash[target-num]!=0)10 return {i-1,hash[target-num]-1};11 else12 hash[num]=i;13 ++i;14 }15 return {};16 }17};python:
xxxxxxxxxx91class Solution:2 def twoSum(self, nums: List[int], target: int) -> List[int]:3 le=len(nums)4 dic=dict()5 for i in range(le):6 if nums[i] in dic:7 return [dic[nums[i]],i]8 else:9 dic[target-nums[i]]=i四个for循环
两组两个for循环,配合哈希表可以通过,时间复杂度
xxxxxxxxxx161class Solution {2public:3 int fourSumCount(vector<int>& nums1, vector<int>& nums2, vector<int>& nums3, vector<int>& nums4) 4 {5 unordered_map<int,int>hash;6 int n=nums1.size();7 for(int i=0;i<n;++i)8 for(int j=0;j<n;++j)9 ++hash[-nums1[i]-nums2[j]];10 int ret=0;11 for(int i=0;i<n;++i)12 for(int j=0;j<n;++j)13 ret+=hash[nums3[i]+nums4[j]];14 return ret;15 }16};简单题,大佬们可以直接跳过
python:
xxxxxxxxxx141class Solution:2 def canConstruct(self, ransomNote: str, magazine: str) -> bool:3 hash={}4 for ch in magazine:5 if ch not in hash:6 hash[ch]=17 else:8 hash[ch]+=19 for ch in ransomNote:10 if ch not in hash or hash[ch]==0:11 return False12 else:13 hash[ch]-=114 return True这一题是给下一题打基础用的
推荐看灵神的视频
C++:
xxxxxxxxxx201class Solution {2public:3 vector<int> twoSum(vector<int>& numbers, int target) 4 {5 int left=0,right=numbers.size()-1;6 int sum;7 while(1)8 {9 sum=numbers[left]+numbers[right];10 if(sum==target)11 {12 return vector<int>{left+1,right+1};13 }14 else if(sum>target)15 --right;16 else 17 ++left;18 }19 }20};python:
xxxxxxxxxx121class Solution:2 def twoSum(self, numbers: List[int], target: int) -> List[int]:3 left=04 right=len(numbers)-15 while 1:6 tmp=numbers[left]+numbers[right]7 if tmp==target:8 return [left+1,right+1]9 elif tmp>target:10 right-=111 else:12 left+=1这题不好做 😫
C++:
xxxxxxxxxx341class Solution {2public:3 vector<vector<int>> threeSum(vector<int>& nums) 4 {5 sort(nums.begin(),nums.end());6 vector<vector<int>>ret;7 for(int i=0;i<nums.size();++i)8 {9 while(i>0&&i<nums.size()&&nums[i]==nums[i-1])10 ++i;11 if(i==nums.size())12 break;13 int left=i+1,right=nums.size()-1;14 while(left<right)15 {16 int sum=-(nums[left]+nums[right]);17 if(sum==nums[i]&&left<right)18 {19 vector<int>tmp={nums[i],nums[left],nums[right]};20 ret.emplace_back(tmp);21 while(right>0&&left<right&&nums[right-1]==nums[right])22 --right;23 if(right>0)24 --right;25 }26 else if(sum<nums[i])27 --right;28 else 29 ++left;30 }31 }32 return ret;33 }34};python:
xxxxxxxxxx271class Solution:2 def threeSum(self, nums: List[int]) -> List[List[int]]:3 nums.sort()4 ret=[]5 le=len(nums)6 idx=07 while idx<le-2:8 while idx>0 and idx<le and nums[idx]==nums[idx-1]:9 idx+=110 if(idx>=le-2):11 break12 target=-nums[idx]13 left=idx+114 right=le-115 while left<right:16 add=nums[left]+nums[right]17 if add==target:18 ret.append([nums[idx],nums[left],nums[right]])19 while right>left and nums[right]==nums[right-1]:20 right-=121 right-=122 elif add>target:23 right-=124 else:25 left+=126 idx+=127 return ret
双指针交换就行
C++:
xxxxxxxxxx161class Solution {2public:3 void reverseString(vector<char>& s) 4 {5 int left=0;6 int right=s.size()-1;7 while(left<right)8 {9 s[left]=s[left]^s[right];10 s[right]=s[left]^s[right];11 s[left]=s[left]^s[right];12 ++left;13 --right;14 }15 }16};Javascript:
xxxxxxxxxx171/**2 * @param {character[]} s3 * @return {void} Do not return anything, modify s in-place instead.4 */5var reverseString = function(s) 6{7 let n=s.length;8 let left=0,right=n-1;9 while(left<right)10 {11 let tmp=s[left];12 s[left]=s[right];13 s[right]=tmp;14 ++left;15 --right;16 }17};xxxxxxxxxx171class Solution {2public:3 string reverseStr(string s, int k) 4 {5 int n=0;6 int flag=1;7 for(;flag;++n)8 {9 auto beg=s.begin()+2*n*k;10 if(2*n*k+k>=s.size())11 flag=0;12 auto end=s.begin()+min((int)s.size(),2*n*k+k);13 reverse(beg,end);14 }15 return s;16 }17};算法很简单,可以拿这个检验一下自己对库函数的熟悉程度
Javascript:不用库函数
xxxxxxxxxx161/**2 * @param {string} s3 * @return {string}4 */5var replaceSpace = function(s) 6{7 let tmp="";8 for(var i=0;i<s.length;++i)9 {10 if(s[i]!=' ')11 tmp+=s[i];12 else13 tmp+="%20";14 }15 return tmp;16};直接调用库函数:
xxxxxxxxxx81/**2 * @param {string} s3 * @return {string}4 */5var replaceSpace = function(s) 6{7 return s.replaceAll(' ',"%20");8};python也有这个库函数:
xxxxxxxxxx31class Solution:2 def replaceSpace(self, s: str) -> str:3 return s.replace(" ","%20")JavaScript:
xxxxxxxxxx301/**2 * @param {string} s3 * @return {string}4 */5var reverseWords = function(s) 6{7 let arr=[];8 let tmp="",ret="";9 for(var i=0;i<s.length;++i)10 {11 if(s[i]!==" ")12 {13 tmp+=s[i];14 }15 else if(tmp!="")16 {17 arr.push(tmp);18 tmp="";19 }20 }21 if(tmp!="")22 arr.push(tmp);23 for(var i=arr.length-1;i>=0;--i)24 {25 ret+=arr[i];26 if(i!=0)27 ret+=" ";28 }29 return ret;30};大佬的调用内置函数解法:
xxxxxxxxxx31var reverseWords = function(s) {2 return s.trim().split(/\s+/).reverse().join(' ');3};split( /\s+/)的意思是将字符串以满足/\s+/这个正则表达式的字符来分割为一个数组。
分割满足条件包括:
制表符,换行符,回车符,垂直制表符,换页符在内的一个至无穷个类空格字符。
其中:
\s表示:匹配任何空白字符,包括空格、制表符、换页符等等。等价于[ \f\n\r\t\v]。
+表示:匹配前面的子表达式一次或多次。
split():是js的一个用于把一个字符串分割成字符串数组的方法。join()方法就是将array数据中每个元素都转为字符串,用自定义的连接符分割KMP算法的经典例题
方法1:KMP算法
next数组 样例1:
| a | a | b | a | a | f |
|---|---|---|---|---|---|
| 0 | 1 | 0 | 1 | 2 | 0 |
next数组 样例2:
| a | a | b | a | a | a | b |
|---|---|---|---|---|---|---|
| 0 | 1 | 0 | 1 | 2 | 2 | 3 |
遍历next数组的指针指向下标为j处时,遇到不匹配,就回退到下标next[j-1]处
next数组的构造过程
i指向后缀表的末尾,j指向前缀表的末尾,每轮循环需要判断前后缀表的末尾元素能否加入前后缀表中,也就是比较needle[i]和needle[j]是否相等
前缀表和后缀表等长,末尾元素加入前后缀表后,长度都是j+1
初始化i=1,j=0
xxxxxxxxxx401class Solution {2public:3 int strStr(string haystack, string needle) //KMP4 {5 int n=haystack.size(),m=needle.size();6 //构造next数组7 vector<int>next(m);8 int i=1,j=0;9 while(i<m)10 {11 if(needle[i]==needle[j])12 next[i++]=++j;13 else if(j==0)14 next[i++]=0;15 else16 j=next[j-1];17 }18 //打印next数组检验19 // for(int& num:next)20 // cout<<num<<' ';21 //匹配字符串22 i=0,j=0;23 while(i<n&&j<m)24 {25 if(haystack[i]==needle[j])26 {27 ++i;28 ++j;29 }30 else if(j==0)31 ++i;32 else33 j=next[j-1];34 }35 if(j==m)36 return i-m;37 else38 return -1;39 }40};方法2:Rabin-Karp算法
这个算法实际上就是哈希表,ChatGPT的解释:
Rabin-Karp算法是一种字符串匹配算法,用于在一个文本串中查找一个模式串的出现位置。
算法的基本思想是通过哈希函数将模式串和文本串的子串进行比较。首先计算模式串的哈希值,然后依次计算文本串中所有长度为模式串长度的子串的哈希值,并与模式串的哈希值进行比较。如果哈希值相同,再逐个比较子串和模式串的每个字符是否相同,直到找到完全匹配的子串或者遍历完所有子串。
算法的优点是可以在平均情况下达到线性时间复杂度O(n+m),其中n是文本串的长度,m是模式串的长度。然而,在最坏情况下,算法的时间复杂度为O((n-m+1)m),即当哈希值的冲突比较多时,效率会下降。
总结来说,Rabin-Karp算法通过哈希函数加速字符串匹配,适用于处理长文本串和短模式串的情况。它在实际应用中常被用于字符串搜索、文本编辑器等领域。
xxxxxxxxxx131class Solution {2public:3 int strStr(string haystack, string needle) 4 {5 unordered_map<string,int>hash;6 hash[needle]=1;7 int m=needle.size(),n=haystack.size();8 for(int i=0;i<=n-m;++i)9 if(hash[haystack.substr(i,m)]==1)10 return i;11 return -1;12 }13};方法1:双指针
xxxxxxxxxx251class Solution:2 def repeatedSubstringPattern(self, s: str) -> bool:3 i=0 # 慢指针4 j=1 # 快指针5 n=len(s)6 tmp=0 # 记录flag改变时j的值,以便恢复7 flag=0 # flag=0表示未找到重复的部分 =1表示找到了8 while j<n:9 if flag==0:10 if s[i]==s[j] and n%j==0:11 flag=112 tmp=j13 i+=114 j+=115 else:16 j+=117 else:18 if s[i]!=s[j]:19 i=020 j=tmp+121 flag=022 else:23 i+=124 j+=125 return flag==1方法2:转化为字符串匹配问题
xxxxxxxxxx71class Solution {2public:3 bool repeatedSubstringPattern(string s) 4 {5 return (s+s).find(s,1)!=s.size();6 }7};方法3:转化为字符串匹配问题,并利用KMP算法
xxxxxxxxxx461class Solution {2public:3 int strStr(string haystack, string needle) //KMP4 {5 int n=haystack.size(),m=needle.size();6 //构造next数组7 vector<int>next(m);8 int i=1,j=0;9 while(i<m)10 {11 if(needle[i]==needle[j])12 next[i++]=++j;13 else if(j==0)14 next[i++]=0;15 else16 j=next[j-1];17 }18 //打印next数组检验19 // for(int& num:next)20 // cout<<num<<' ';21 //匹配字符串22 i=0,j=0;23 while(i<n&&j<m)24 {25 if(haystack[i]==needle[j])26 {27 ++i;28 ++j;29 }30 else if(j==0)31 ++i;32 else33 j=next[j-1];34 }35 if(j==m)36 return i-m;37 else38 return -1;39 }40 bool repeatedSubstringPattern(string s) 41 {42 string hay=s+s;43 hay.erase(0,1);44 return strStr(hay,s)!=s.size()-1;45 }46};笨人的这段代码比较乱,建议去看方法2,更易理解
xxxxxxxxxx841class Solution {2public:3 bool isNumber(string s) 4 {5 int idx=0;6 if(s[idx]=='+'||s[idx]=='-')7 ++idx;8 int flag1=0;//是否存在整数位9 int flag2=0;//判断小数点是否出现,对应小数点前没有数字的情况10 int flag3=0;//判断小数点是否出现,对应小数点前有数字的情况11 int flag4=0;//小数点后有没有整数位12 if(idx==s.size())13 return false;14 if(s[idx]=='.')15 {16 ++idx;17 flag2=1;18 }19 if(idx==s.size())20 return false;21 while(idx<s.size())22 {23 if(s[idx]>='0'&&s[idx]<='9')24 {25 ++idx;26 flag1=1;27 }28 else29 break;30 }31 if(idx==s.size())32 {33 return flag1;34 }35 if(flag2==1&&flag1==0)36 return false;37 if(flag2==1&&idx<s.size()&&s[idx]=='.')38 return false;39 if(flag2==0&&idx<s.size()&&s[idx]=='.')40 {41 ++idx;42 flag3=1;43 }44 while(idx<s.size())45 {46 if(s[idx]>='0'&&s[idx]<='9')47 {48 ++idx;49 flag4=1;50 }51 else52 break;53 }54 if(flag1==0&&flag4==0)55 return false;56 57 if(idx<s.size()&&(s[idx]=='e'||s[idx]=='E'))58 {59 ++idx;60 if(idx==s.size())61 return false;62 if(s[idx]=='+'||s[idx]=='-')63 ++idx;64 if(idx==s.size())65 return false;66 int flag5=0;67 while(idx<s.size())68 {69 if(s[idx]>='0'&&s[idx]<='9')70 {71 ++idx;72 flag5=1;73 }74 else75 break;76 }77 if(flag5==1&&idx==s.size())78 return true;79 }80 if(idx==s.size())81 return true;82 return false;83 }84};0ms 5.8MB
(图片出自力扣官方题解)

最后只有cur==2||cur==3||cur==5||cur==8时返回true
xxxxxxxxxx861class Solution {2public:3 bool isNumber(string s) 4 {5 int cur=0;//当前状态6 int idx=0;//当前下标7 for(;idx<s.size();++idx)8 {9 switch(cur)10 {11 case 0:12 if(s[idx]=='+'||s[idx]=='-')13 cur=1;14 else if(s[idx]=='.')15 cur=4;16 else if(s[idx]>='0'&&s[idx]<='9')17 cur=2;18 else19 return false;20 break;21 case 1:22 if(s[idx]>='0'&&s[idx]<='9')23 cur=2;24 else if(s[idx]=='.')25 cur=4;26 else27 return false;28 break;29 case 2:30 if(s[idx]>='0'&&s[idx]<='9')31 cur=2;32 else if(s[idx]=='.')33 cur=3;34 else if(s[idx]=='e'||s[idx]=='E')35 cur=6;36 else37 return false;38 break; 39 case 3:40 if(s[idx]=='e'||s[idx]=='E')41 cur=6;42 else if(s[idx]>='0'&&s[idx]<='9')43 cur=5;44 else 45 return false;46 break;47 case 4:48 if(s[idx]>='0'&&s[idx]<='9')49 cur=5;50 else51 return false;52 break;53 case 5:54 if(s[idx]>='0'&&s[idx]<='9')55 cur=5;56 else if(s[idx]=='e')57 cur=6;58 else59 return false;60 break;61 case 6:62 if(s[idx]=='+'||s[idx]=='-')63 cur=7;64 else if(s[idx]>='0'&&s[idx]<='9')65 cur=8;66 else 67 return false;68 break;69 case 7:70 if(s[idx]>='0'&&s[idx]<='9')71 cur=8;72 else73 return false;74 break;75 case 8:76 if(s[idx]>='0'&&s[idx]<='9')77 cur=8;78 else79 return false;80 break;81 }82 }83 //此时idx==s.size()84 return cur==2||cur==3||cur==5||cur==8;85 }86};0ms 5.9MB
代码粘贴自评论区大佬
正在表达式的构造耗时很长,所以建议采用第二段代码,避免重复构造
xxxxxxxxxx61class Solution {2public:3 bool isNumber(string str) {4 return regex_match(str, regex("[+-]?(\\d+\\.?\\d*|\\.\\d+)([Ee][+-]?\\d+)?"));5 }6};1884ms,259.3MB
xxxxxxxxxx101class Solution {2public:3 static const regex pattern;4
5 bool isNumber(string str) {6 return regex_match(str, pattern);7 }8};9
10const regex Solution::pattern("[+-]?(\\d+\\.?\\d*|\\.\\d+)([Ee][+-]?\\d+)?");12ms 9MB
正则表达式
xxxxxxxxxx161class Solution {2public:3 static const regex pattern4;4 static const regex pattern6;5 string validIPAddress(string queryIP) 6 {7 if(regex_match(queryIP,pattern4))8 return "IPv4";9 else if(regex_match(queryIP,pattern6))10 return "IPv6";11 else12 return "Neither"; 13 }14};15const regex Solution::pattern4("((25[0-5]|2[0-4][0-9]|1\\d\\d|[1-9]?\\d)\\.){3}(25[0-5]|2[0-4][0-9]|1\\d\\d|[1-9]?\\d)");16const regex Solution::pattern6("([0-9a-fA-F]{1,4}\\:){7}([0-9a-fA-F]{1,4})");字典树的经典例题
xxxxxxxxxx631class TrieNode{2public:3 char ch;4 vector<TrieNode*>next;5 TrieNode(char ch_=0):ch(ch_),next(27,nullptr){}6};7class Trie {8public:9 TrieNode* root;10 Trie() {11 root=new TrieNode;12 }13 14 void insert(string word) {15 TrieNode* cur=root;16 for(char& w:word)17 {18 int idx=w-'a';19 if(cur->next[idx]!=nullptr)20 cur=cur->next[idx];21 else22 {23 cur->next[idx]=new TrieNode(w);24 cur=cur->next[idx];25 }26 }27 cur->next[26]=new TrieNode;//标识单词的结尾28 }29 30 bool search(string word) {31 TrieNode* cur=root;32 for(char& w:word)33 {34 int idx=w-'a';35 if(cur->next[idx]==nullptr)36 return false;37 else38 cur=cur->next[idx];39 }40 return cur->next[26]!=nullptr;41 }42 43 bool startsWith(string prefix) {44 TrieNode* cur=root;45 for(char& w:prefix)46 {47 int idx=w-'a';48 if(cur->next[idx]==nullptr)49 return false;50 else51 cur=cur->next[idx];52 }53 return true;54 }55};56
57/**58 * Your Trie object will be instantiated and called as such:59 * Trie* obj = new Trie();60 * obj->insert(word);61 * bool param_2 = obj->search(word);62 * bool param_3 = obj->startsWith(prefix);63 */前缀树+记忆化搜索
xxxxxxxxxx711class TrieNode{//字典树节点2public:3 vector<TrieNode*>next;4 TrieNode():next(27,nullptr){}5};6class Solution {7public:8 vector<string> findAllConcatenatedWordsInADict(vector<string>& words) {9 TrieNode* root=new TrieNode;10 for(string& str:words)//将所有的单词插入前缀树(字典树)11 {12 if(str.size()==0)13 continue;14 TrieNode* cur=root;15 for(char& ch:str)16 {17 int idx=ch-'a';18 if(cur->next[idx]==nullptr)19 {20 cur->next[idx]=new TrieNode;21 cur=cur->next[idx];22 }23 else24 cur=cur->next[idx];25 }26 cur->next[26]=new TrieNode;//标识单词的结尾27 }28 vector<string>ret;29 for(string& str:words)//查找符合题意的字符串30 {31 if(str.size()==0)32 continue;33 queue<pair<int,int>>que;//利用队列34 que.push(make_pair(-1,-2));35 vector<int>isvisited(str.size());36 while(!que.empty())37 {38 39 int pos=que.front().first+1;40 int pre=que.front().second;41 que.pop();42 if(pos!=str.size())//记忆化搜索,否则会超时43 {44 if(isvisited[pos]==0)45 isvisited[pos]=1;46 else47 continue;48 }49 TrieNode*cur=root;50 int i;51 for(i=pos;i<str.size();++i)52 {53 int idx=str[i]-'a';54 if(cur->next[idx]!=nullptr)55 cur=cur->next[idx];56 else 57 break; 58 if(cur->next[26]!=nullptr)59 que.push(make_pair(i,pos));60 61 }62 if(pos==str.size()&&pre>0)63 {64 ret.emplace_back(str);65 break;66 }67 }68 }69 return ret;70 }71};前缀树+DFS+记忆化搜索
xxxxxxxxxx751class TrieNode{2public:3 bool isend;//是不是单词的结尾4 vector<TrieNode*>next;5 TrieNode(bool isend_=false):isend(isend_),next(26,nullptr){}6};7class Solution {8public:9 TrieNode* root;10 vector<string> findAllConcatenatedWordsInADict(vector<string>& words) {11 root=new TrieNode;12 sort(words.begin(),words.end(),[&](string& a,string& b){13 return a.size()<b.size();14 });15 vector<string>ret;16 for(string& str:words)17 {18 // if(str.size()==0)19 // continue;20 vector<bool>isvisited(str.size(),false);21 bool flag=false;22 function<void(int)>dfs=[&](int i)23 {24 if(flag)25 return;26 isvisited[i]=true;27 TrieNode* p=root;28 for(int j=i;j<str.size();++j)29 {30 31 int idx=str[j]-'a';32 if(p->next[idx]!=nullptr)33 {34 p=p->next[idx];35 }36 else37 {38 return;39 }40 if(j==str.size()-1)41 {42 if(i!=0&&p->isend)43 {44 ret.emplace_back(str);45 flag=true;46 }47 return;48 }49 if(p->isend)50 {51 if(!isvisited[j+1])52 dfs(j+1);53 }54 if(flag)55 return;56 }57 };58 dfs(0);59 TrieNode* p=root;60 for(char& ch:str)61 {62 int idx=ch-'a';63 if(p->next[idx]!=nullptr)64 p=p->next[idx];65 else66 {67 p->next[idx]=new TrieNode;68 p=p->next[idx];69 }70 }71 p->isend=true;72 }73 return ret;74 }75};AC自动机的经典例题
xxxxxxxxxx791class TrieNode{2public:3 TrieNode* fail;4 vector<TrieNode*>next;5 bool isend;6 TrieNode():fail(nullptr),next(26,nullptr),isend(false){}7};8class StreamChecker {9public:10 TrieNode* root;11 TrieNode* pos;12 StreamChecker(vector<string>& words) 13 {14 root=new TrieNode;15 root->fail=root;16 pos=root;17 for(string& word:words)//第一次遍历:构造字典树18 {19 TrieNode* p=root;20 for(char& ch:word)21 {22 int idx=ch-'a';23 if(p->next[idx]==nullptr)24 p->next[idx]=new TrieNode;25 p=p->next[idx];26 }27 p->isend=true;28 }29 //设置fail指针 注意:这里必须广度优先遍历,不允许深度优先遍历30 queue<TrieNode*>q;31 q.push(root);32 while(!q.empty())33 {34 TrieNode* front=q.front();35 q.pop();36 for(int i=0;i<26;++i)37 {38 if(front->next[i]==nullptr)39 continue;40 else41 q.push(front->next[i]);42 TrieNode* f=front->fail;43 while(f!=root&&f->next[i]==nullptr)44 f=f->fail;45 if(front!=root&&f->next[i]!=nullptr)46 front->next[i]->fail=f->next[i];47 else48 front->next[i]->fail=root;49 }50 } 51 }52 bool query(char letter) 53 {54 int idx=letter-'a';55 while(pos!=root&&pos->next[idx]==nullptr)56 {57 pos=pos->fail;58 }59 TrieNode* tmp=pos;60 if(pos->next[idx]!=nullptr)61 pos=pos->next[idx];62 while(tmp!=root)63 {64 if(tmp->next[idx]!=nullptr&&tmp->next[idx]->isend)65 return true;66 else67 tmp=tmp->fail;68 }69 if(tmp->next[idx]!=nullptr&&tmp->next[idx]->isend)70 return true;71 return false;72 }73};74
75/**76 * Your StreamChecker object will be instantiated and called as such:77 * StreamChecker* obj = new StreamChecker(words);78 * bool param_1 = obj->query(letter);79 */相当基础的栈的应用
xxxxxxxxxx311class Solution {2public:3 stack<char>st;4 bool isValid(string s) 5 {6 char ch;7 for(int i=0;s[i]!=0;i++)8 {9 if(s[i]=='('||s[i]=='['||s[i]=='{')10 st.push(s[i]);11 else12 {13 if(st.empty())14 return false;15 else 16 {17 ch=st.top();18 st.pop();19 if(abs(ch-s[i])<3&&ch!=s[i])20 continue;21 else22 return false;23 }24 }25 }26 if(st.empty())27 return true;28 else29 return false;30 }31};xxxxxxxxxx281class Solution {2public:3 string removeDuplicates(string s) 4 {5 stack<char>sta;6 int len=0;7 for(char& ch:s)8 {9 if(sta.empty()||sta.top()!=ch)10 {11 sta.push(ch);12 ++len;13 }14 else15 {16 sta.pop();17 --len;18 }19 }20 string ret(len,0);21 for(int i=len-1;i>=0;--i)22 {23 ret[i]=sta.top();24 sta.pop();25 }26 return ret;27 }28};以下为王道考研数据结构的笔记:栈在表达式求值中的应用
序号表示各个运算符的执行顺序
xxxxxxxxxx41((15 ÷ (7-(1 + 1)))×3) - (2+(1 + 1)) 中缀表达式2③ ② ① ④ ⑦ ⑥ ⑤3① ② ③ ④ ⑤ ⑥ ⑦415 7 1 1 + - ÷ 3 × 2 1 1 + + - 后缀表达式




C++:
xxxxxxxxxx381class Solution {2public:3 int evalRPN(vector<string>& tokens) 4 {5 stack<int>sta;6 for(string& s:tokens)7 {8 if(s=="+"||s=="-"||s=="*"||s=="/")9 {10 int a=sta.top();11 sta.pop();12 int b=sta.top();13 sta.pop();14 switch(s[0])15 {16 case '*':17 sta.push(b*a);18 break;19 case '/':20 sta.push(b/a);21 break;22 case '+':23 sta.push(b+a);24 break;25 case '-':26 sta.push(b-a);27 break;28 }29 }30 else31 {32 int num=stoi(s);33 sta.push(num);34 }35 }36 return sta.top();37 }38};xxxxxxxxxx851class Solution {2public:3 int calculate(string s) 4 {5 stack<char>oper;6 stack<int>nums;7 int tmp=0;8 for(int i=0;i<s.size();++i)9 {10 char ch=s[i];11 if(ch>='0'&&ch<='9')12 {13 tmp*=10;14 tmp+=ch-'0';15 if(i+1==s.size()||s[i+1]<'0'||s[i+1]>'9')16 {17 nums.push(tmp);18 tmp=0;19 }20 }21 else22 {23 if(ch=='(')24 oper.push('(');25 else if(ch=='+'||ch=='-')26 {27 if(ch=='-')28 {29 int j=i-1;30 while(j>=0&&s[j]==' ')31 --j;32 if(j==-1||s[j]=='(')33 nums.push(0);34 }35 while(!oper.empty()&&(oper.top()=='+'||oper.top()=='-'))36 {37 int right=nums.top();38 nums.pop();39 int left=nums.top();40 nums.pop();41 if(oper.top()=='+')42 nums.push(left+right);43 else44 nums.push(left-right);45 oper.pop();46 }47 oper.push(ch);48 }49 else if(ch==')')50 {51 while(!oper.empty())52 {53 if(oper.top()=='(')54 {55 oper.pop();56 break;57 }58 int right=nums.top();59 nums.pop();60 int left=nums.top();61 nums.pop();62 if(oper.top()=='+')63 nums.push(left+right);64 else65 nums.push(left-right);66 oper.pop();67 }68 }69 }70 }71 while(!oper.empty())72 {73 int right=nums.top();74 nums.pop();75 int left=nums.top();76 nums.pop();77 if(oper.top()=='+')78 nums.push(left+right);79 else80 nums.push(left-right);81 oper.pop();82 }83 return nums.top();84 }85};代码在上一题的基础上改了一下,可以支持对正负数的+-*/和括号运算
xxxxxxxxxx1091class Solution {2public:3 int calculate(string s) 4 {5 stack<char>oper;6 stack<int>nums;7 int tmp=0;8 for(int i=0;i<s.size();++i)9 {10 char ch=s[i];11 if(ch>='0'&&ch<='9')12 {13 tmp*=10;14 tmp+=ch-'0';15 if(i+1==s.size()||s[i+1]<'0'||s[i+1]>'9')16 {17 nums.push(tmp);18 tmp=0;19 }20 }21 else22 {23 if(ch=='(')24 oper.push('(');25 else if(ch=='+'||ch=='-')26 {27 if(ch=='-')28 {29 int j=i-1;30 while(j>=0&&s[j]==' ')31 --j;32 if(j==-1||s[j]=='(')33 nums.push(0);34 }35 while(!oper.empty()&&(oper.top()=='+'||oper.top()=='-'||oper.top()=='*'||oper.top()=='/'))36 {37 int right=nums.top();38 nums.pop();39 int left=nums.top();40 nums.pop();41 if(oper.top()=='+')42 nums.push(left+right);43 else if(oper.top()=='-')44 nums.push(left-right);45 else if(oper.top()=='*')46 nums.push(left*right);47 else48 nums.push(left/right);49 oper.pop();50 }51 oper.push(ch);52 }53 else if(ch=='*'||ch=='/')54 {55 while(!oper.empty()&&(oper.top()=='*'||oper.top()=='/'))56 {57 int right=nums.top();58 nums.pop();59 int left=nums.top();60 nums.pop();61 if(oper.top()=='*')62 nums.push(left*right);63 else64 nums.push(left/right);65 oper.pop();66 }67 oper.push(ch);68 }69 else if(ch==')')70 {71 while(!oper.empty())72 {73 if(oper.top()=='(')74 {75 oper.pop();76 break;77 }78 int right=nums.top();79 nums.pop();80 int left=nums.top();81 nums.pop();82 if(oper.top()=='+')83 nums.push(left+right);84 else85 nums.push(left-right);86 oper.pop();87 }88 }89 }90 }91 while(!oper.empty())92 {93 int right=nums.top();94 nums.pop();95 int left=nums.top();96 nums.pop();97 if(oper.top()=='+')98 nums.push(left+right);99 else if(oper.top()=='-')100 nums.push(left-right);101 else if(oper.top()=='*')102 nums.push(left*right);103 else104 nums.push(left/right);105 oper.pop();106 }107 return nums.top();108 }109};先序遍历模板
C++:
xxxxxxxxxx281/**2 * Definition for a binary tree node.3 * struct TreeNode {4 * int val;5 * TreeNode *left;6 * TreeNode *right;7 * TreeNode() : val(0), left(nullptr), right(nullptr) {}8 * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}9 * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}10 * };11 */12class Solution {13public:14 vector<int> preorderTraversal(TreeNode* root) 15 {16 vector<int>ret;17 function<void(TreeNode*)>dfs=[&](TreeNode* head)18 {19 if(head==nullptr)20 return;21 ret.emplace_back(head->val);22 dfs(head->left);23 dfs(head->right);24 };25 dfs(root);26 return ret;27 }28};python:
xxxxxxxxxx171# Definition for a binary tree node.2# class TreeNode:3# def __init__(self, val=0, left=None, right=None):4# self.val = val5# self.left = left6# self.right = right7class Solution:8 def preorderTraversal(self, root: Optional[TreeNode]) -> List[int]:9 arr=[]10 def dfs(TreeNode):11 if TreeNode==None:12 return13 arr.append(TreeNode.val)14 dfs(TreeNode.left)15 dfs(TreeNode.right)16 dfs(root)17 return arr中序遍历模板:
和上面代码基本一样,交换它们的顺序:
xxxxxxxxxx31dfs(head->left);2ret.emplace_back(head->val);3dfs(head->right);后序遍历:
xxxxxxxxxx31dfs(head->left);2dfs(head->right);3ret.emplace_back(head->val); 用栈模拟递归的过程
写出二叉树的非递归遍历很难么?这次让你不再害怕非递归!|二叉树的非递归遍历 | 二叉树的遍历迭代法 | 前序与中(参考视频)
注意:因为栈是先进后出的,先将右子节点入栈,再让左子节点入栈
C++:
xxxxxxxxxx201class Solution {2public:3 vector<int> preorderTraversal(TreeNode* root) 4 {5 stack<TreeNode*>sta;6 sta.push(root);7 vector<int>ret;8 while(!sta.empty())9 {10 TreeNode* cur=sta.top();11 sta.pop();12 if(cur==nullptr)13 continue;14 ret.emplace_back(cur->val);15 sta.push(cur->right);16 sta.push(cur->left);17 }18 return ret;19 }20};Python:
xxxxxxxxxx121class Solution:2 def preorderTraversal(self, root: Optional[TreeNode]) -> List[int]:3 arr=[]4 stack=[root]5 while len(stack)!=0:6 cur=stack.pop()7 if cur==None:8 continue9 arr.append(cur.val)10 stack.append(cur.right)11 stack.append(cur.left)12 return arr前序遍历是按照 中左右 遍历的
如果把前序遍历代码中
xxxxxxxxxx21sta.push(cur->right);2sta.push(cur->left);颠倒顺序, 变成
xxxxxxxxxx21sta.push(cur->left);2sta.push(cur->right);遍历顺序变成 中右左
最后的arr数组进行反转,遍历序列就会变成 左右中 后序遍历序列
C++:
xxxxxxxxxx211class Solution {2public:3 vector<int> postorderTraversal(TreeNode* root) 4 {5 stack<TreeNode*>sta;6 sta.push(root);7 vector<int>ret;8 while(!sta.empty())9 {10 TreeNode* cur=sta.top();11 sta.pop();12 if(cur==nullptr)13 continue;14 ret.emplace_back(cur->val);15 sta.push(cur->left);16 sta.push(cur->right); 17 }18 reverse(ret.begin(),ret.end());19 return ret;20 }21};Python:
xxxxxxxxxx131class Solution:2 def postorderTraversal(self, root: Optional[TreeNode]) -> List[int]:3 arr=[]4 stack=[root]5 while len(stack)!=0:6 cur=stack.pop()7 if cur==None:8 continue9 arr.append(cur.val)10 stack.append(cur.left)11 stack.append(cur.right)12 arr=arr[::-1]13 return arrxxxxxxxxxx481class Solution {2public:3 vector<int> inorderTraversal(TreeNode* root) 4 {5 int flag=1;//1为左模式,2为右模式6 stack<TreeNode*>sta;7 vector<int>ret;8 if(root==nullptr)9 return ret;10 TreeNode* p=root;11 sta.push(p);//孩子节点的入栈由父节点负责,头节点是例外12 while(1)13 {14 if(flag==1)//左模式15 {16 if(p->left!=nullptr)17 {18 sta.push(p->left);19 p=p->left;20 }21 else22 {23 flag=2;24 ret.emplace_back(p->val);25 sta.pop();26 }27 }28 else//右模式29 {30 if(p->right!=nullptr)31 {32 flag=1;33 sta.push(p->right);34 p=p->right;35 }36 else37 {38 if(sta.empty())39 break;40 p=sta.top();41 sta.pop();42 ret.emplace_back(p->val);43 }44 }45 }46 return ret;47 }48};xxxxxxxxxx251typedef struct TreeNode treenode;2class Solution {3public:4 vector<vector<int>> ret;5 queue<pair<treenode*,int>> que;6 vector<vector<int>> levelOrder(TreeNode* root) 7 {8 que.push(make_pair(root,0));9 if(root==NULL)10 return ret;11 while(!que.empty())12 {13 treenode* cur=que.front().first;14 int floor=que.front().second;15 ret.resize(floor+1);16 que.pop();17 if(cur->left!=NULL)18 que.push(make_pair(cur->left,floor+1));19 if(cur->right!=NULL)20 que.push(make_pair(cur->right,floor+1));21 ret[floor].emplace_back(cur->val);22 }23 return ret;24 }25};xxxxxxxxxx171class Solution {2public:3 TreeNode* invertTree(TreeNode* root) 4 {5 function<void(TreeNode*)>dfs=[&](TreeNode* cur)6 {7 swap(cur->left,cur->right);8 if(cur->left!=nullptr)9 dfs(cur->left);10 if(cur->right!=nullptr)11 dfs(cur->right);12 };13 if(root!=nullptr)14 dfs(root);15 return root;16 }17};xxxxxxxxxx281class Solution {2public:3 bool isSymmetric(TreeNode* root) 4 {5 bool ret=true;6 function<void(TreeNode*,TreeNode*)>dfs=[&](TreeNode*p1,TreeNode*p2)7 {8 if(!ret)9 return;10 if(p1!=nullptr&&p2!=nullptr)11 {12 if(p1->val!=p2->val)13 {14 ret=false;15 return;16 }17 dfs(p1->right,p2->left);18 dfs(p1->left,p2->right);19 }20 else if(p1==nullptr&&p2==nullptr)21 return;22 else23 ret=false;24 };25 dfs(root->left,root->right);26 return ret;27 }28};xxxxxxxxxx181class Solution {2public:3 int maxDepth(TreeNode* root) 4 {5 int ret=0;6 function<void(TreeNode*,int)>dfs=[&](TreeNode* cur,int idx)7 {8 ret=max(ret,idx);9 if(cur->left!=nullptr)10 dfs(cur->left,idx+1);11 if(cur->right!=nullptr)12 dfs(cur->right,idx+1);13 };14 if(root!=nullptr)15 dfs(root,1);16 return ret;17 }18};xxxxxxxxxx231class Solution {2public:3 int minDepth(TreeNode* root) 4 {5 int ret=0x7fffffff;6 function<void(TreeNode*,int)>dfs=[&](TreeNode* cur,int idx)7 {8 if(cur->left!=nullptr)9 dfs(cur->left,idx+1);10 if(cur->right!=nullptr)11 dfs(cur->right,idx+1);12 if(cur->left==nullptr&&cur->right==nullptr)13 {14 ret=min(ret,idx);15 }16 };17 if(root!=nullptr)18 dfs(root,1);19 else20 ret=0;21 return ret;22 }23};(思路同力扣官方题解)
xxxxxxxxxx441class Solution {2public:3 int countNodes(TreeNode* root) 4 {5 if(root==nullptr)6 return 0;7 int ret=0;8 int h=2;//计算二叉树的层数9 TreeNode* p=root;10 while(p->right!=nullptr)11 {12 p=p->right;13 ++h;14 }15 int left=1,right;16 for(int i=1;i<h;++i)17 left*=2;18 right=left*2-1;19 while(left<=right)20 {21 int aver=(left+right)/2;22 vector<int>bits(h);23 int tmp=aver;24 for(int i=h-1;i>=0;--i)25 {26 bits[i]=tmp%2;27 tmp/=2;28 }29 p=root;30 for(int i=1;i<h;++i)31 {32 if(bits[i]==1)33 p=p->right;34 else35 p=p->left;36 }37 if(p==nullptr)38 right=aver-1;39 else40 left=aver+1;41 }42 return right;43 }44};时间复杂度:
二叉树的深度
首先需要
然后进行二分查找, 每次查找都要访问
所以总的时间复杂度
因为开辟了长为
这个方法利用递归, 更容易写😋
利用性质:一棵深度为
另外, 在C++中, 1 << n
xxxxxxxxxx241class Solution {2public:3 int countNodes(TreeNode* root) 4 {5 if(root==nullptr)6 return 0;7 int ldepth=1,rdepth=1;8 TreeNode* p=root;9 while(p->left!=nullptr)10 {11 p=p->left;12 ++ldepth;13 }14 p=root;15 while(p->right!=nullptr)16 {17 p=p->right;18 ++rdepth;19 }20 if(ldepth==rdepth)21 return (1 << ldepth) - 1;22 else return countNodes(root->left)+countNodes(root->right)+1;23 }24};时间复杂度:
考虑最坏的情况, 也就是二叉树最大层次只有一个节点的情况, 总共需要递归
空间复杂度:
在最坏的情况下, 需要递归
xxxxxxxxxx201class Solution {2public:3 bool isBalanced(TreeNode* root) 4 {5 bool ret=true;6 function<int(TreeNode*)>depth=[&](TreeNode* head)7 {8 if(!ret)9 return -1;10 if(head==nullptr)11 return 0;12 int ld=depth(head->left);13 int rd=depth(head->right);14 ret&=abs(ld-rd)<2;15 return max(ld,rd)+1;16 };17 depth(root);18 return ret;19 }20};回溯法+dfs
使用to_string()函数(包含于头文件#include<string>),快速将整数转化为字符串
xxxxxxxxxx281class Solution {2public:3 vector<string> binaryTreePaths(TreeNode* root) 4 {5 vector<string>ret;6 string str;7 function<void(TreeNode*)>dfs=[&](TreeNode* cur)8 {9 string tmp=to_string(cur->val);10 if(cur!=root)11 str+="->";12 str+=tmp;13 if(cur->left==nullptr&&cur->right==nullptr)14 {15 ret.emplace_back(str);16 str=str.substr(0,max<int>(0,str.size()-2-tmp.size()));17 return;18 }19 if(cur->left!=nullptr)20 dfs(cur->left);21 if(cur->right!=nullptr)22 dfs(cur->right);23 str=str.substr(0,max<int>(0,str.size()-2-tmp.size()));24 };25 dfs(root);26 return ret;27 }28};这题还挺简单的😏
xxxxxxxxxx221class Solution {2public:3 int sumOfLeftLeaves(TreeNode* root) 4 {5 int ret=0;6 //tag=1时表示为左孩子7 function<void(TreeNode*,int)>dfs=[&](TreeNode* cur,int tag) 8 {9 if(tag==1&&cur->left==nullptr&&cur->right==nullptr)10 {11 ret+=cur->val;12 return;13 }14 if(cur->left!=nullptr)15 dfs(cur->left,1);16 if(cur->right!=nullptr)17 dfs(cur->right,0);18 };19 dfs(root,0);20 return ret;21 }22};方法1:失败案例(原因:利用对于完全二叉树的节点编号解题,编号过大造成溢出)
idx的意义是节点在对应完全二叉树中的编号n
深度h和n的关系为
左孩子的编号满足
右孩子的编号满足
xxxxxxxxxx361using ll = unsigned long long; 2class Solution {3public:4 int findBottomLeftValue(TreeNode* root) 5 {6 //idx的意义是节点在对应完全二叉树中的编号7 int max_depth=1;8 int ret=-1;9 ll ret_idx=0;//越小越好10 function<void(TreeNode*,int)>dfs=[&](TreeNode* cur,ll idx)11 {12 if(cur->left==nullptr&&cur->right==nullptr)13 {14 int depth=(int)(log(idx)/log(2))+1;15 max_depth=max(max_depth,depth);16 if(depth==max_depth)17 {18 if(ret_idx<(1<<(depth-1)))19 ret_idx=(1<<(depth))-1;20 if(idx<=ret_idx)21 {22 ret_idx=idx;23 ret=cur->val;24 }25 }26 return;27 }28 if(cur->left!=nullptr)29 dfs(cur->left,idx<<1);30 if(cur->right!=nullptr)31 dfs(cur->right,(idx<<1)+1);32 };33 dfs(root,1);34 return ret;35 }36};方法2: 乖乖用层序遍历,不整花里胡哨的方法才能AC
xxxxxxxxxx251class Solution {2public:3 int findBottomLeftValue(TreeNode* root) 4 {5 int max_depth=0;6 int ret=-1;7 queue<pair<TreeNode*,int>>que;8 que.push({root,1});9 while(!que.empty())10 {11 auto cur=que.front();12 que.pop();13 if(cur.second>max_depth)14 {15 max_depth=cur.second;16 ret=cur.first->val;17 }18 if(cur.first->left!=nullptr)19 que.push({cur.first->left,cur.second+1});20 if(cur.first->right!=nullptr)21 que.push({cur.first->right,cur.second+1});22 }23 return ret;24 }25};方法3:整点花里胡哨的,用回溯法
利用性质: 在深度优先搜索中,同一层位于左侧的节点总是最先被搜索到
xxxxxxxxxx261class Solution {2public:3 int findBottomLeftValue(TreeNode* root) 4 {5 int ret=-1;6 int max_depth=0;7 function<void(TreeNode*,int)>dfs=[&](TreeNode* cur,int depth)8 {9 if(cur->left==nullptr&&cur->right==nullptr)10 {11 if(depth>max_depth)12 {13 max_depth=depth;14 ret=cur->val;15 }16 return;17 }18 if(cur->left!=nullptr)19 dfs(cur->left,depth+1);20 if(cur->right!=nullptr)21 dfs(cur->right,depth+1);22 };23 dfs(root,1);24 return ret;25 }26};简单题,回溯解决,大佬可以跳过
xxxxxxxxxx341class Solution {2public:3 bool hasPathSum(TreeNode* root, int targetSum) 4 {5 if(root==nullptr)6 return false;7 int add=root->val;8 bool flag=false;9 function<void(TreeNode*)>dfs=[&](TreeNode* cur)10 {11 if(flag)12 return;13 if(cur->left==nullptr&&cur->right==nullptr)14 {15 if(add==targetSum)16 flag=true;17 }18 if(cur->left!=nullptr)19 {20 add+=cur->left->val;21 dfs(cur->left);22 add-=cur->left->val;23 }24 if(cur->right!=nullptr)25 {26 add+=cur->right->val;27 dfs(cur->right);28 add-=cur->right->val;29 }30 };31 dfs(root);32 return flag;33 }34};还是回溯,上面的代码稍微改动即可
xxxxxxxxxx391class Solution {2public:3 vector<vector<int>> pathSum(TreeNode* root, int targetSum) 4 {5 vector<vector<int>>ret;6 vector<int>vec;7 if(root==nullptr)8 return ret;9 vec.emplace_back(root->val);10 int add=root->val;11 function<void(TreeNode*)>dfs=[&](TreeNode* cur)12 {13 if(cur->left==nullptr&&cur->right==nullptr)14 {15 if(add==targetSum)16 ret.emplace_back(vec);17 return;18 }19 if(cur->left!=nullptr)20 {21 add+=cur->left->val;22 vec.emplace_back(cur->left->val);23 dfs(cur->left);24 vec.pop_back();25 add-=cur->left->val;26 }27 if(cur->right!=nullptr)28 {29 add+=cur->right->val;30 vec.emplace_back(cur->right->val);31 dfs(cur->right);32 vec.pop_back();33 add-=cur->right->val;34 }35 };36 dfs(root);37 return ret;38 }39};leetcode106从中序与后序遍历序列构造二叉树
回溯法,有点复杂
xxxxxxxxxx141class Solution {2public:3 TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) 4 {5 function<TreeNode*(int,int,int,int)>dfs=[&](int ileft,int iright,int pleft,int pright)6 {7 if(ileft>iright||pleft>pright)8 return (TreeNode*)nullptr;9 int igap=find(inorder.begin()+ileft,inorder.begin()+iright+1,postorder[pright])-inorder.begin();10 return new TreeNode(postorder[pright],dfs(ileft,igap-1,pleft,pleft+igap-ileft-1),dfs(igap+1,iright,pleft+igap-ileft,pright-1));11 };12 return dfs(0,inorder.size()-1,0,postorder.size()-1);13 }14};leetcode105 从前序与中序遍历序列构造二叉树
和上题一样的思路
xxxxxxxxxx141class Solution {2public:3 TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) 4 {5 function<TreeNode*(int,int,int,int)>dfs=[&](int pl,int pr,int il,int ir)6 {7 if(pl>pr||il>ir)8 return (TreeNode*)nullptr;9 int gap=find(inorder.begin()+il,inorder.begin()+ir+1,preorder[pl])-inorder.begin();10 return new TreeNode(preorder[pl],dfs(pl+1,gap-il+pl,il,gap-1),dfs(gap-il+pl+1,pr,gap+1,ir));11 };12 return dfs(0,preorder.size()-1,0,inorder.size()-1);13 }14};xxxxxxxxxx221class Solution {2public:3 TreeNode* constructMaximumBinaryTree(vector<int>& nums) 4 {5 function<TreeNode*(int,int)>dfs=[&](int le,int ri)6 {7 if(le>ri)8 return (TreeNode*)nullptr;9 int max_element=0x80000000,max_index=-1;10 for(int i=le;i<=ri;++i)11 {12 if(nums[i]>max_element)13 {14 max_index=i;15 max_element=nums[i];16 }17 }18 return new TreeNode(max_element,dfs(le,max_index-1),dfs(max_index+1,ri));19 };20 return dfs(0,nums.size()-1);21 }22};一样的回溯思路
xxxxxxxxxx181class Solution {2public:3 TreeNode* mergeTrees(TreeNode* root1, TreeNode* root2) 4 {5 function<TreeNode*(TreeNode*,TreeNode*)>dfs=[&](TreeNode* p1,TreeNode* p2)6 {7 if(p1!=nullptr&&p2!=nullptr)8 return new TreeNode(p1->val+p2->val,dfs(p1->left,p2->left),dfs(p1->right,p2->right));9 if(p2==nullptr&&p1!=nullptr)10 return new TreeNode(p1->val,dfs(p1->left,nullptr),dfs(p1->right,nullptr));11 if(p1==nullptr&&p2!=nullptr)12 return new TreeNode(p2->val,dfs(nullptr,p2->left),dfs(nullptr,p2->right));13 return (TreeNode*)nullptr;14 };15 TreeNode* p1=root1,*p2=root2;16 return dfs(p1,p2);17 }18};简单题,大佬请跳过
xxxxxxxxxx171class Solution {2public:3 TreeNode* searchBST(TreeNode* root, int val) 4 {5 TreeNode* p=root;6 while(p!=nullptr)7 {8 if(val==p->val)9 return p;10 else if(val<p->val)11 p=p->left;12 else13 p=p->right;14 }15 return nullptr;16 }17};别小看这题,坑巨多
xxxxxxxxxx331class Solution {2public:3 bool isValidBST(TreeNode* root) 4 {5 bool ret=true;6 int downinf=1,upinf=1;7 function<void(TreeNode*,int,int)>dfs=[&](TreeNode* cur,int up,int down)8 {9 if(!ret||cur==nullptr)10 return;11 if(cur->val<=down&&downinf==0||cur->val>=up&&upinf==0)12 ret=false;13 if(upinf==1)14 {15 upinf=0;16 dfs(cur->left,cur->val,down);17 upinf=1;18 }19 else20 dfs(cur->left,cur->val,down);21 if(downinf==1)22 {23 downinf=0;24 dfs(cur->right,up,cur->val);25 downinf=1;26 }27 else28 dfs(cur->right,up,cur->val);29 };30 dfs(root,0,0);31 return ret;32 }33};相当于求二叉树中序遍历序列相邻元素的最小绝对差
xxxxxxxxxx191class Solution {2public:3 int getMinimumDifference(TreeNode* root) 4 {5 int last=-1000000;6 int ret=0x7fffffff;7 function<void(TreeNode*)>dfs=[&](TreeNode* cur)//中序遍历8 {9 if(cur==nullptr)10 return;11 dfs(cur->left);12 ret=min(ret,abs(cur->val-last));13 last=cur->val;14 dfs(cur->right);15 };16 dfs(root);17 return ret;18 }19};采用中序遍历就行
xxxxxxxxxx531class Solution {2public:3 vector<int> findMode(TreeNode* root) 4 {5 int pre=-200000;6 int cnt=1,ret=1;7 vector<int>vec;8 function<void(TreeNode*)>dfs=[&](TreeNode* cur)9 {10 if(cur==nullptr)11 return;12 dfs(cur->left);13 if(cur->val==pre)14 {15 ++cnt;16 }17 else if(pre!=-200000)18 {19 if(cnt>ret)20 {21 vec.resize(0);22 vec.emplace_back(pre);23 ret=cnt;24 }25 else if(cnt==ret)26 {27 vec.emplace_back(pre);28 }29 cnt=1;30 pre=cur->val;31 }32 else33 {34 cnt=1;35 pre=cur->val;36 }37 dfs(cur->right);38 };39 dfs(root);40 if(cnt>ret)41 {42 vec.resize(0);43 vec.emplace_back(pre);44 ret=cnt;45 }46 else if(cnt==ret)47 {48 vec.emplace_back(pre);49 }50 cnt=1;51 return vec;52 }53};直接回溯
xxxxxxxxxx281class Solution {2public:3 TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) 4 {5 TreeNode* ret=nullptr;6 int depth=-1;7 function<int(TreeNode*,int)>dfs=[&](TreeNode* cur,int dep)8 {9 if(cur==nullptr)10 return 0;11 int status=0;12 if(cur==p)13 status|=2;14 else if(cur==q)15 status|=1;16 status|=dfs(cur->left,dep+1);17 status|=dfs(cur->right,dep+1);18 if(status==3&&dep>depth)19 {20 depth=dep;21 ret=cur;22 }23 return status;24 };25 dfs(root,0);26 return ret;27 }28};和上一题差不多,这题是二叉搜索树,可以利用性质简化
用指针t从根节点开始采用二分搜索,直到发现t==p||t==q,或者p和q分别位于t两侧
xxxxxxxxxx191class Solution {2public:3 TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) 4 {5 TreeNode* t=root;6 while(t!=nullptr)7 {8 if(t==p||t==q)9 return t;10 if(t->val>p->val&&t->val>q->val)11 t=t->left;12 else if(t->val<p->val&&t->val<q->val)13 t=t->right;14 else15 return t;16 }17 return nullptr;18 }19};简单题,大佬可跳过
xxxxxxxxxx331class Solution {2public:3 TreeNode* insertIntoBST(TreeNode* root, int val) 4 {5 TreeNode* p=root;6 if(p==nullptr)7 return new TreeNode(val);8 while(1)9 {10 if(val>p->val)11 {12 if(p->right!=nullptr)13 p=p->right;14 else15 {16 p->right=new TreeNode(val);17 return root; 18 }19 }20 else21 {22 if(p->left!=nullptr)23 p=p->left;24 else25 {26 p->left=new TreeNode(val);27 return root;28 }29 }30 }31 return root;32 }33};xxxxxxxxxx531class Solution {2public:3 TreeNode* deleteNode(TreeNode* root, int key) 4 {5 TreeNode* dummyhead=new TreeNode(0,root,nullptr);6 TreeNode* pre=dummyhead;7 TreeNode* cur=root;8 while(cur!=nullptr&&cur->val!=key)9 {10 pre=cur;11 if(cur->val>key)12 cur=cur->left;13 else14 cur=cur->right;15 }16 if(cur==nullptr)17 {18 delete dummyhead;19 return root;20 }21 if(cur->left==nullptr)22 {23 if(pre->left==cur)24 pre->left=cur->right;25 else26 pre->right=cur->right;27 }28 else if(cur->right==nullptr)29 {30 if(pre->left==cur)31 pre->left=cur->left;32 else33 pre->right=cur->left;34 }35 else36 {37 TreeNode* tmp=cur->left->right;38 TreeNode* p=cur->right;39 cur->left->right=cur->right;40 if(pre->left==cur)41 pre->left=cur->left;42 else43 pre->right=cur->left;44 while(p->left!=nullptr)45 p=p->left;46 p->left=tmp;47 }48 delete cur;49 TreeNode* ret=dummyhead->left;50 delete dummyhead;51 return ret;52 }53};C++:
xxxxxxxxxx271class Solution {2public:3 vector<vector<int>> combine(int n, int k) 4 {5 vector<vector<int>>ret;6 vector<int>sel;7 sel.reserve(n);8 function<void(int)> dfs=[&](int idx)9 {10 if(n-idx+1<k-sel.size())//剪枝11 return;12 if(idx>n+1)//递归上限13 return;14 if(sel.size()==k)15 {16 ret.emplace_back(sel);17 return;18 }19 dfs(idx+1);//不取当前数字20 sel.emplace_back(idx);21 dfs(idx+1);//取当前数字22 sel.pop_back();23 };24 dfs(1);25 return ret;26 }27};python: 要注意几个global的使用
xxxxxxxxxx261num=0 # 统计已经加入数组arr的元素数量2ret=[]3arr=[]4class Solution:5 def combine(self, n: int, k: int) -> List[List[int]]:6 global num,ret,arr7 ret=[]8 arr=[]9 num=010 def dfs(idx: int):11 global num,ret,arr12 if num>k:13 return14 if idx==n+1:15 if num==k:16 ret.append(arr.copy())17 return18 dfs(idx+1)19 num+=120 arr.append(idx)21 dfs(idx+1)22 num-=123 arr.pop(num)24 dfs(1)25 return ret26
xxxxxxxxxx281class Solution {2public:3 vector<vector<int>> combinationSum3(int k, int n) 4 {5 vector<vector<int>>ret;6 vector<int>sel;7 sel.reserve(k);8 int add=0;9 function<void(int)>dfs=[&](int idx)10 {11 if(idx>10)12 return;13 if(add==n&&sel.size()==k)14 {15 ret.emplace_back(sel);16 return;17 }18 dfs(idx+1);19 add+=idx;20 sel.emplace_back(idx);21 dfs(idx+1);22 add-=idx;23 sel.pop_back();24 };25 dfs(1);26 return ret;27 }28};方法1: 两层for循环模拟枚举
xxxxxxxxxx341class Solution {2public:3 vector<string> letterCombinations(string digits) 4 {5 vector<string> str={"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};6 vector<string> vec;7 for(int i=0;i<digits.size();++i)8 {9 int idx=digits[i]-'0';10 if(i==0)11 {12 for(int j=0;j<str[idx].size();++j)13 {14 vec.emplace_back(str[idx].substr(j,1));15 }16 }17 else18 {19 int j=0;20 for(;j<vec.size()&&vec[j].size()<=i;++j)21 {22 for(auto ch:str[idx])23 {24 string tmp=vec[j];25 tmp+=ch;26 vec.emplace_back(tmp);27 }28 }29 vec.erase(vec.begin(),vec.begin()+j);30 }31 }32 return vec;33 }34};方法2:递归回溯
xxxxxxxxxx271class Solution {2public:3 vector<string> letterCombinations(string digits) 4 {5 vector<vector<char>>vec={{},{},{'a','b','c'},{'d','e','f'},{'g','h','i'},{'j','k','l'},{'m','n','o'},{'p','q','r','s'},{'t','u','v'},{'w','x','y','z'}};6 vector<string>ret;7 string s;8 function<void(int)>dfs=[&](int idx)9 {10 if(idx==digits.size())11 {12 if(s.size()!=0)13 ret.emplace_back(s);14 return;15 }16 vector<char>&tmp=vec[digits[idx]-'0'];17 for(char& ch:tmp)18 {19 s.push_back(ch);20 dfs(idx+1);21 s.pop_back();22 }23 };24 dfs(0);25 return ret;26 }27};xxxxxxxxxx391class Solution {2public:3 vector<vector<int>> combinationSum(vector<int>& candidates, int target) 4 {5 vector<vector<int>>ret;6 vector<int>vec;7 int add=0;8 function<void(int)>dfs=[&](int idx)9 {10 if(idx==candidates.size())11 {12 if(add==target)13 ret.emplace_back(vec);14 return;15 }16 dfs(idx+1);17 int cnt=0;18 while(1)19 {20 if(add+candidates[idx]<=target)21 {22 add+=candidates[idx];23 vec.emplace_back(candidates[idx]);24 ++cnt;25 dfs(idx+1); 26 }27 else28 break;29 }30 for(int i=0;i<cnt;++i)31 {32 add-=candidates[idx];33 vec.pop_back();34 }35 };36 dfs(0);37 return ret;38 }39};xxxxxxxxxx331class Solution {2public:3 vector<vector<int>> combinationSum2(vector<int>& candidates, int target) 4 {5 vector<vector<int>>ret;6 vector<int>vec;7 int add=0;8 sort(candidates.begin(),candidates.end());//避免出现重复的组合9 function<void(int)>dfs=[&](int idx)10 {11 if(add>target)12 return;13 if(add==target)14 {15 ret.emplace_back(vec);16 return;17 }18 if(idx==candidates.size())19 return;20 vec.emplace_back(candidates[idx]);21 add+=candidates[idx];22 dfs(idx+1);23 vec.pop_back();24 add-=candidates[idx];25 int i=idx+1;26 while(i<candidates.size()&&candidates[i]==candidates[i-1])27 ++i;28 dfs(i);29 };30 dfs(0);31 return ret;32 }33};xxxxxxxxxx521class Solution {2public:3 int len;4 string str;5 vector<vector<string>> ret;6 bool ispalind(string s)7 {8 int slen=s.size();9 int i=0,j=slen-1;10 for(;i<j;++i,--j)11 {12 if(s[i]!=s[j])13 return false;14 }15 return true;16 }17 void dfs(int idx,vector<int>punc)18 {19 if(idx==len)20 {21 vector<string> tmp;22 int last=0;23 for(int i=1;i<=punc.size();++i)24 {25 if(i==punc.size()||punc[i]==1)26 {27 string st=str.substr(last,i-last);28 if(!ispalind(st))29 return;30 tmp.emplace_back(st);31 last=i;32 }33 }34 ret.emplace_back(tmp);35 return;36 }37 else38 {39 dfs(idx+1,punc);40 punc[idx]=1;41 dfs(idx+1,punc);42 }43 }44 vector<vector<string>> partition(string s) 45 {46 len=s.size();47 str=s;48 vector<int>punc(len);49 dfs(1,punc);50 return ret;51 }52};xxxxxxxxxx431class Solution {2public:3 vector<string> restoreIpAddresses(string s) 4 {5 int n=s.size();6 string tmp;7 vector<string>ret;8 int cnt=0;9 function<void(int)>dfs=[&](int i)10 {11 if(cnt==4||i==n)12 {13 if(cnt==4&&i==n)14 ret.emplace_back(tmp);15 return;16 }17 for(int j=i;j<n&&j<i+3;++j)18 {19 string add=s.substr(i,j-i+1);20 int num=stoi(add);21 if(num<=255&&s[i]!='0'||s[i]=='0'&&j==i)22 {23 int flag=0;24 if(tmp.size()!=0)25 {26 tmp+='.';27 flag=1;28 }29 tmp+=add;30 ++cnt;31 dfs(j+1);32 --cnt;33 if(flag)34 tmp.erase(tmp.size()-add.size()-1,add.size()+1);35 else36 tmp.erase(tmp.size()-add.size(),add.size());37 }38 }39 };40 dfs(0);41 return ret;42 }43};xxxxxxxxxx251class Solution {2public:3 vector<vector<int>> ret;4 vector<int>num;5 int n;6 void make(vector<int> tem,int p)7 {8 if(p==n)9 {10 ret.push_back(tem);11 return;12 }13 make(tem,p+1);14 tem.push_back(num[p]);15 make(tem,p+1);16 }17 vector<vector<int>> subsets(vector<int>& nums) 18 {19 n=nums.size();20 num=nums;21 vector<int> tem;22 make(tem,0);23 return ret;24 }25};xxxxxxxxxx261class Solution {2public:3 vector<vector<int>> subsetsWithDup(vector<int>& nums) 4 {5 vector<vector<int>>ret;6 vector<int>tmp;7 sort(nums.begin(),nums.end());8 int n=nums.size();9 function<void(int)>dfs=[&](int idx)10 {11 if(idx==n)12 {13 ret.emplace_back(tmp);14 return;15 }16 tmp.emplace_back(nums[idx]);17 dfs(idx+1);18 tmp.pop_back();19 while(idx+1<n&&nums[idx+1]==nums[idx])20 ++idx;21 dfs(idx+1);22 };23 dfs(0);24 return ret;25 }26};xxxxxxxxxx331class Solution {2public:3 vector<vector<int>> findSubsequences(vector<int>& nums) 4 {5 int n=nums.size();6 vector<vector<int>>ret;7 vector<int>tmp;8 function<void(int)>dfs=[&](int idx)9 {10 if(idx==n)11 {12 if(tmp.size()>=2)13 ret.emplace_back(tmp);14 return;15 }16 unordered_map<int,int>hash;17 for(int i=idx;i<n;++i)18 {19 if(hash[nums[i]]==0&&(tmp.size()==0||nums[i]>=tmp.back()))20 {21 hash[nums[i]]=1;22 tmp.emplace_back(nums[i]);23 dfs(i+1);24 tmp.pop_back();25 }26 }27 if(tmp.size()>=2)28 ret.emplace_back(tmp);29 };30 dfs(0);31 return ret;32 }33};xxxxxxxxxx301class Solution {2public:3 vector<vector<int>> permute(vector<int>& nums) 4 {5 vector<vector<int>> ret;6 vector<int>isvalid(nums.size(),0);7 vector<int>cur;8 auto dfs=[&]()9 {10 if(cur.size()==nums.size())11 {12 ret.emplace_back(cur);13 return;14 }15 for(int i=0;i<nums.size();++i)16 {17 if(isvalid[i]==0)18 {19 cur.emplace_back(nums[i]);20 isvalid[i]=1;21 dfs();22 cur.pop_back();23 isvalid[i]=0;24 }25 }26 };27 dfs();28 return ret;29 }30};方法1:在得到全排列数组后进行整体去重
xxxxxxxxxx431using ll=long long;2class Solution {3public:4 vector<vector<int>> permuteUnique(vector<int>& nums) 5 {6 vector<ll>quan(nums.size());7 quan[0]=1;8 for(int i=1;i<nums.size();++i)9 quan[i]=quan[i-1]*11;10 unordered_map<ll,int>hash;11 vector<int>vec(nums.size());12 vector<int>cur;13 vector<vector<int>>ret;14 ll key=0;15 function<void(int)>dfs=[&](int idx)16 {17 if(idx==nums.size())18 {19 if(hash[key]==0)20 {21 hash[key]=1;22 ret.emplace_back(cur);23 }24 return;25 }26 for(int i=0;i<nums.size();++i)27 {28 if(vec[i]==0)29 {30 vec[i]=1;31 cur.emplace_back(nums[i]);32 key+=quan[idx]*nums[i];33 dfs(idx+1);34 key-=quan[idx]*nums[i];35 vec[i]=0;36 cur.pop_back();37 }38 }39 };40 dfs(0);41 return ret;42 }43};60ms,8.8MB
方法2:在递归的同一层内避免插入相同元素到数组中,有效避免出现重复
xxxxxxxxxx361class Solution {2public:3 vector<vector<int>> permuteUnique(vector<int>& nums) 4 {5 int n=nums.size();6 vector<int>isvisited(n);7 vector<int>tmp;8 vector<vector<int>>ret;9 function<void(int)>dfs=[&](int idx)10 {11 if(idx==n)12 {13 ret.emplace_back(tmp);14 return;15 }16 unordered_map<int,int>hash;17 for(int i=0;i<n;++i)18 {19 if(isvisited[i]==0)20 {21 if(hash[nums[i]]==0)22 {23 hash[nums[i]]=1;24 isvisited[i]=1;25 tmp.emplace_back(nums[i]);26 dfs(idx+1);27 tmp.pop_back();28 isvisited[i]=0;29 }30 }31 }32 };33 dfs(0);34 return ret;35 }36};8ms,10.9MB
xxxxxxxxxx411class Solution {2public:3 vector<string> findItinerary(vector<vector<string>>& tickets) 4 {5 int n=tickets.size();6 sort(tickets.begin(),tickets.end(),[&](vector<string>&a,vector<string>&b){return a[1]<b[1];});7 string loca="JFK";8 vector<int>isUsed(n);9 vector<string>ret;10 vector<string>ret1;11 ret.emplace_back(loca);12 int flag=0;13 function<void(int)>dfs=[&](int idx)14 {15 if(flag)16 return;17 if(idx==n)18 {19 ret1=ret;20 flag=1;21 return;22 }23 for(int i=0;i<n;++i)24 {25 if(tickets[i][0]==loca&&isUsed[i]==0)26 {27 isUsed[i]=1;28 string tmp=loca;29 loca=tickets[i][1];30 ret.emplace_back(loca);31 dfs(idx+1);32 ret.pop_back();33 loca=tmp;34 isUsed[i]=0;35 }36 }37 };38 dfs(0);39 return ret1;40 }41};xxxxxxxxxx581class Solution {2public:3 vector<vector<string>> solveNQueens(int n) 4 {5 vector<vector<string>>ret;6 vector<string>graph(n);7 for(auto& _vec:graph)8 _vec.assign(n,'.');9 vector<int>row(n);10 function<void(int)>dfs=[&](int col)11 {12 if(col==n)13 {14 ret.emplace_back(graph);15 return;16 }17 for(int i=0;i<n;++i)18 {19 if(row[i]!=0)20 continue;21 int flag=0;22 for(int j=0;j<n;++j)23 {24 int k=i+col-j;25 if(k<0||k>=n)26 continue;27 if(graph[j][k]=='Q')28 {29 flag=1;30 break;31 }32 }33 if(flag==1)34 continue;35 for(int j=0;j<n;++j)36 {37 int k=j+col-i;38 if(k<0||k>=n)39 continue;40 if(graph[j][k]=='Q')41 {42 flag=1;43 break;44 }45 }46 if(flag==1)47 continue;48 row[i]=1;49 graph[i][col]='Q';50 dfs(col+1);51 row[i]=0;52 graph[i][col]='.';53 }54 };55 dfs(0);56 return ret;57 }58};数独棋盘:
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | |
|---|---|---|---|---|---|---|---|---|---|
| 0 | |||||||||
| 1 | |||||||||
| 2 | |||||||||
| 3 | |||||||||
| 4 | |||||||||
| 5 | |||||||||
| 6 | |||||||||
| 7 | |||||||||
| 8 |
判断是否属于同一个x/3*10+y/3的大小
xxxxxxxxxx591class Solution {2public:3 void solveSudoku(vector<vector<char>>& board) 4 {5 int flag=0;//已经填好的标记6 function<void(int,int)>dfs=[&](int x,int y)7 {8 if(flag)9 return;10 if(x==9)11 {12 flag=1;13 return;14 }15 if(board[x][y]=='.')16 {17 vector<int>isvalid(10);18 for(int i=0;i<=8;++i)//处理同行同列19 {20 if(board[i][y]!='.')21 isvalid[board[i][y]-'0']=1;22 if(board[x][i]!='.')23 isvalid[board[x][i]-'0']=1;24 }25 for(int i=0;i<3;++i)26 {27 for(int j=0;j<3;++j)28 {29 if(board[x/3*3+i][y/3*3+j]!='.')30 isvalid[board[x/3*3+i][y/3*3+j]-'0']=1;31 }32 }33 for(int i=1;i<=9;++i)34 {35 if(isvalid[i]==0)36 {37 board[x][y]=i+'0';38 if(y==8)//访问下一个格子39 dfs(x+1,0);40 else41 dfs(x,y+1);42 if(flag==1)43 return;44 else45 board[x][y]='.';46 }47 }48 }49 else50 {51 if(y==8)//访问下一个格子52 dfs(x+1,0);53 else54 dfs(x,y+1);55 }56 };57 dfs(0,0);58 }59};排序 + 双指针 + 贪心
xxxxxxxxxx211class Solution {2public:3 int findContentChildren(vector<int>& g, vector<int>& s) 4 {5 sort(g.begin(),g.end());6 sort(s.begin(),s.end());7 int i=0,j=0;8 int ret=0;9 for(;i<g.size()&&j<s.size();++i)10 {11 while(j<s.size()&&s[j]<g[i])12 ++j;13 if(j<s.size()&&s[j]>=g[i])14 {15 ++j;16 ++ret;17 }18 }19 return ret;20 }21};python:
xxxxxxxxxx271class Solution:2 def wiggleMaxLength(self, nums: List[int]) -> int:3 le=len(nums)4 i=15 flag=1 # 1表示增,2表示减6 ret=17 while i<le and nums[i]==nums[i-1]:8 i+=19 if i<le and nums[i]>nums[i-1]:10 flag=111 elif i<le:12 flag=013 else:14 return 115 i=116 while i<le:17 if flag==1:18 while i<le and nums[i]>=nums[i-1]:19 i+=120 ret+=121 flag=022 else:23 while i<le and nums[i]<=nums[i-1]:24 i+=125 ret+=126 flag=127 return ret这里考虑局部最优解
从左到右遍历一次nums数组,遍历到第i个元素时,add的含义是选择nums[i]的条件下考虑前i个元素的最大子数组和
然后用ret记录add的最大值
C++:
xxxxxxxxxx131class Solution {2public:3 int maxSubArray(vector<int>& nums) 4 {5 int ret=nums[0],add=nums[0];6 for(int i=1;i<nums.size();++i)7 {8 add=max(add+nums[i],nums[i]);9 ret=max(ret,add);10 }11 return ret;12 }13};python:
xxxxxxxxxx81class Solution:2 def maxSubArray(self, nums: List[int]) -> int:3 add=04 ret=-1000005 for num in nums:6 add=max(add+num,num)7 ret=max(ret,add)8 return ret动态规划章节也包含了这道题
方法1:贪心
相当于截取prices数组中的所有上升子数组,求出它们的首尾元素之差并求和
C:
xxxxxxxxxx101int maxProfit(int* prices, int pricesSize)2{3 int ret=0;4 for(int i=1;i<pricesSize;++i)5 {6 if(prices[i]>prices[i-1])7 ret+=prices[i]-prices[i-1];8 }9 return ret;10}python:
xxxxxxxxxx91class Solution:2 def maxProfit(self, prices: List[int]) -> int:3 pre=inf4 profit=05 for num in prices:6 if num-pre>0:7 profit+=num-pre8 pre=num9 return profit方法2:奇妙的动态规划
dfs[i][0]表示第i天结束不持有股票的最大利润pair.first
dfs[i][1]表示第i天结束持有股票的最大利润pair.second
C++:一维数组递推
xxxxxxxxxx161class Solution {2public:3 int maxProfit(vector<int>& prices) 4 {5 int len=prices.size();6 vector<pair<int,int>> dfs(len);7 dfs[0].first=0;8 dfs[0].second=-prices[0];9 for(int i=1;i<len;++i)10 {11 dfs[i].first=max(dfs[i-1].first,dfs[i-1].second+prices[i]);12 dfs[i].second=max(dfs[i-1].second,dfs[i-1].first-prices[i]);13 }14 return dfs[len-1].first;15 }16};python:将一维数组压缩为更新两个变量
xxxxxxxxxx101class Solution:2 def maxProfit(self, prices: List[int]) -> int:3 have=-prices[0] # 当前持有股票的最大利润4 notHave=0 # 当前不持有股票的最大利润5 for i in range(1,len(prices)):6 tp1=max(have,notHave-prices[i])7 tp2=max(notHave,have+prices[i])8 have=tp19 notHave=tp210 return notHave简单贪心,只需维护bound作为当前能到达的最远位置
C:
xxxxxxxxxx201bool canJump(int* nums, int numsSize)2{3 if(numsSize==1)4 return true;5 for(int i=0;i<numsSize-1;i++)6 {7 if(nums[i]==0)8 {9 int p=0;10 for(int j=i;j>=0;j--)11 {12 if(nums[i-j]>j)13 p=1;14 }15 if(p==0)16 return false;17 }18 }19 return true;20}python:
xxxxxxxxxx81class Solution:2 def canJump(self, nums: List[int]) -> bool:3 bound=04 for idx,num in enumerate(nums):5 if idx>bound:6 return False7 bound=max(bound,idx+num)8 return TrueC:
xxxxxxxxxx191int jump(int* nums, int numsSize)2{3 int dis1=0,dis2=0;4 if(numsSize==1)5 return 0;6 for(int i=1;i<numsSize;i++)7 {8 int far=0;9 for(int j=dis2;j<=dis1;j++)10 {11 far=far>nums[j]+j?far:nums[j]+j;12 }13 dis2=dis1+1;14 dis1=far;15 if(dis1>=numsSize-1)16 return i;17 }18 return 0;19}你可能都没意识到你用了贪心算法, 就不小心AC了
python:
xxxxxxxxxx161class Solution:2 def largestSumAfterKNegations(self, nums: List[int], k: int) -> int:3 nums=sorted(nums)4 idx=05 while idx<len(nums) and nums[idx]<0 and k>0:6 nums[idx]*=-17 idx+=18 k-=19 if k==0:10 return sum(nums)11 elif idx==len(nums):12 nums[idx-1]*=(-1)**k13 return sum(nums)14 nums=sorted(nums)15 nums[0]*=(-1)**k16 return sum(nums)难度蹭蹭上涨了
据说用C++写
贪心:
C++:
时间复杂度
xxxxxxxxxx351class Solution {2public:3 int canCompleteCircuit(vector<int>& gas, vector<int>& cost) 4 {5 int n=gas.size();6 vector<int>vec(n);7 for(int i=0;i<n;++i)8 vec[i]=gas[i]-cost[i];9 int begin=0,end=0;//双指针,左闭右闭10 int add=0;//当前油箱汽油量11 int flag=0;//flag==1代表end已经越过n回到012 while(begin!=end||flag==0)13 {14 add+=vec[end];15 if(add<0)16 {17 if(flag==1)18 return -1;19 add=0;20 ++end;21 if(end==n)22 return -1;23 begin=end;24 continue;25 }26 ++end;27 if(end==n)28 {29 end=0;30 flag=1;31 } 32 }33 return begin;34 }35};方法1:自己的复杂方法
把ratings数组视为一个波, 各个下标处对应的数值为该处波的高度
一次遍历,找到所有的波谷下标装入队列
然后从队列逐个取出下标,从波谷向两侧遍历直到到达波峰, 对于严格上升的点糖果数为上一个位置的糖果数+1,平缓的点糖果数为1
一个位置的糖果数可能被多次计算,取其中的最大值
C++:
xxxxxxxxxx431class Solution {2public:3 int candy(vector<int>& ratings) 4 {5 int n=ratings.size();6 if(n==1)7 return 1;8 queue<int>que;//记录所有波谷的下标9 if(ratings[0]<=ratings[1])10 que.push(0);11 for(int i=1;i<n-1;++i)12 {13 if(ratings[i-1]>=ratings[i]&&ratings[i]<=ratings[i+1])14 que.push(i);15 }16 if(ratings[n-2]>=ratings[n-1])17 que.push(n-1);18 vector<int>candy(n,1);19 while(!que.empty())20 {21 int cur=que.front();22 que.pop();23 candy[cur]=1;24 int left=cur-1;25 for(;left>=0;--left)26 {27 if(ratings[left]>ratings[left+1])28 candy[left]=max(candy[left],candy[left+1]+1);29 else if(ratings[left]<ratings[left+1])30 break;31 }32 int right=cur+1;33 for(;right<n;++right)34 {35 if(ratings[right]>ratings[right-1])36 candy[right]=max(candy[right],candy[right-1]+1);37 else if(ratings[right]<ratings[right-1])38 break;39 }40 }41 return accumulate(candy.begin(),candy.end(),0);42 }43};方法2:大佬们的方法
正反两次遍历
python:
xxxxxxxxxx111class Solution:2 def candy(self, ratings: List[int]) -> int:3 n=len(ratings)4 candies=[1]*n5 for i in range(n): # 只考虑左孩子比右孩子分数低的情况6 if i != 0 and ratings[i]>ratings[i-1]:7 candies[i]=max(candies[i],candies[i-1]+1)8 for i in range(n-1,-1,-1): # 只考虑左孩子比右孩子分数高的1情况9 if i != n-1 and ratings[i]>ratings[i+1]:10 candies[i]=max(candies[i],candies[i+1]+1)11 return sum(candies)简单模拟就行,用生活经验,有10元就优先用10元找零,5元是万能的
python:
xxxxxxxxxx191class Solution:2 def lemonadeChange(self, bills: List[int]) -> bool:3 n5=0 # 5美元钞票数4 n10=0 # 10美元钞票数5 for bill in bills:6 if bill==5:7 n5+=18 elif bill==10:9 n5-=110 n10+=111 else:12 if n10>0:13 n10-=114 n5-=115 else:16 n5-=317 if n5<0:18 return False19 return True有点难😭
搬运自讨论区的精彩解释:https://leetcode.cn/problems/queue-reconstruction-by-height/discussion/comments/1809851
上了第一节体育课,老师给大家排好了体操的队伍,可是大家脑子都很笨,记不清自己在哪,老师说,你就看前面有几个比自己高的就行!就像这样:
xxxxxxxxxx11[[7,0],[4,4],[7,1],[5,0],[6,1],[5,2]]
该上第二节课的时候,大家记住了前面有几个比自己高的,却还是忘记了怎么排,老师见状让学生从高到低排好队,身高一样的,比自己高的越多,越往后面站,像这样:
xxxxxxxxxx11[[7,0],[7,1],[6,1],[5,0],[5,2],[4,4]]
每次让最高的学生出来找自己的位置,第一个高个子[7,0]自然站到了第一个位置:
xxxxxxxxxx11[[7,0]]
而第二个高个子[7,1]知道有一个人大于等于自己的身高,站在了第一个人身后:
xxxxxxxxxx11[[7,0],[7,1]]
第三个人[6,1]想了想,有一个人比自己高,那自己肯定站在第二位,于是就插队,现在也站到了第一个人身后:
xxxxxxxxxx11[[7,0],[6,1],[7,1]]
第四个人[5,0]想了想,没人比自己高,那自己肯定站在第一位,于是就插队,站到了队头:
xxxxxxxxxx11[[5,0],[7,0],[6,1],[7,1]]
第五个人[5,2]想了想,有两个人比自己高,于是就插队,站到了第二个人后面,也就是第三个位置:
xxxxxxxxxx11[[5,0],[7,0],[5,2],[6,1],[7,1]]
第六个人[4,4]看了看眼前的队伍,比自己高的人都在里面,他安心的数着前面有四个人比自己高,心安理得的站到了第四个人身后:
xxxxxxxxxx11[[5,0],[7,0],[5,2],[6,1],[4,4],[7,1]]
其实这道题的大概思路就是这样,只有先让身高高的先进入队伍,后面身高低的才能根据前面高的来找自己的位置
C++:
xxxxxxxxxx191class Solution {2public:3 vector<vector<int>> reconstructQueue(vector<vector<int>>& people) 4 {5 sort(people.begin(),people.end(),[&](vector<int>&a,vector<int>&b)6 {7 return a[0]>b[0]||a[0]==b[0]&&a[1]<b[1];8 });//首先按照h从大到小排序,h相同时按照k从小到大排序9 for(int i=0;i<people.size();++i)10 {11 if(people[i][1]==i)12 continue;13 auto tmp=people[i];14 for(int j=i;j>tmp[1];--j)15 swap(people[j],people[j-1]);16 }17 return people;18 }19};很经典的区间问题
xxxxxxxxxx241class Solution {2public:3 int findMinArrowShots(vector<vector<int>>& points) 4 {5 sort(points.begin(),points.end(),[&](vector<int>& a,vector<int>& b){6 return a[0]<b[0];7 });8 int i=0,ret=0;9 int len=points.size();10 while(i<len)11 {12 int left=points[i][0],right=points[i][1];13 int j=i+1;14 for(;j<len&&points[j][0]<=right;++j)15 {16 left=points[j][0];17 right=min(points[j][1],right);18 }19 ++ret;20 i=j;21 }22 return ret;23 }24};首先按照右边界的坐标从小到大排序,如果右边界坐标相等,就按照左边界从大到小排序
然后从左到右遍历, 对于每个被遍历到的区间,都删除掉它后面所有与之相交的区间
被删除的区间不会再参与遍历
几种已经排好序的样例如下(带x的被删除掉)
xxxxxxxxxx61|--|2|--|3|-----| x4|-----| x5|-------|6|-----|x
xxxxxxxxxx41|-|2|-----| x3|-----|4|-------------|x
C++:
xxxxxxxxxx241class Solution {2public:3 int eraseOverlapIntervals(vector<vector<int>>& intervals) 4 {5 int len=intervals.size();6 sort(intervals.begin(),intervals.end(),[&](vector<int>&a,vector<int>&b){7 return a[1]<b[1]||a[1]==b[1]&&a[0]>b[0];8 });9 int i=0,ret=0;10 while(i<len)11 {12 int j=i+1;13 for(;j<len;++j)14 {15 if(intervals[j][0]<intervals[i][1])16 ++ret;17 else 18 break;19 }20 i=j;21 }22 return ret;23 }24};和上面两题相似,也是区间重叠问题
C++: 自己的糟糕代码
xxxxxxxxxx381class Solution {2public:3 vector<int> partitionLabels(string s) 4 {5 unordered_map<char,int>hash;//记录字母在数组vec中的下标6 vector<pair<int,int>>vec;//记录字母所有出现位置的左边界和右边界7 int len=0;//vec数组的长度8 for(int i=0;i<s.size();++i)9 {10 if(hash.find(s[i])==hash.end())11 {12 hash[s[i]]=len;13 ++len;14 vec.emplace_back(make_pair(i,i));15 }16 else17 vec[hash[s[i]]].second=i;18 }19 sort(vec.begin(),vec.end(),[&](pair<int,int>&a,pair<int,int>&b){20 return a.first<b.first;21 });22 int left=0,right=0;23 vector<int>ret;24 for(auto& p:vec)25 {26 if(p.first>right)27 {28 ret.emplace_back(right-left+1);29 left=p.first;30 right=p.second;31 }32 else33 right=max(right,p.second);34 }35 ret.emplace_back(right-left+1);36 return ret;37 }38};大佬的优雅代码(搬运自https://leetcode.cn/problems/partition-labels/discussion/comments/31356):
xxxxxxxxxx191class Solution {2public:3 vector<int> partitionLabels(string S) {4 vector<int> result;5 unordered_map<char, int> map; //记录char c 和其最后出现位置的 map6 int start = 0, end = 0;7 for (int i = 0; i < S.size(); i ++) {8 map[S[i]] = i;9 }10 for (int i = 0; i < S.size(); i ++) {11 end = max(end, map[S[i]]);12 if (i == end) {13 result.push_back(end - start + 1);14 start = i + 1;15 }16 }17 return result;18 }19};xxxxxxxxxx261class Solution {2public:3 vector<vector<int>> merge(vector<vector<int>>& intervals) 4 {5 sort(intervals.begin(),intervals.end(),[&](vector<int>&a,vector<int>&b){6 return a[0]<b[0];7 });8 int left=intervals[0][0],right=intervals[0][1];9 vector<vector<int>>ret;10 for(auto& vec:intervals)11 {12 if(vec[0]<=right)13 {14 right=max(right,vec[1]);15 }16 else17 {18 ret.emplace_back(vector<int>{left,right});19 left=vec[0];20 right=vec[1];21 }22 }23 ret.emplace_back(vector<int>{left,right});24 return ret;25 }26};方法1:从左到右遍历(作者的笨办法)
将n各个位填入数组(字符串也行),从左到右遍历:
当发现当前位数字比前一位数字小时,就开始修改字符串,修改完字符串就能返回结果
修改规则为:前一位数字减1,当前位数字及之后所有位的数字一律为9
例如6328,遍历到3时,将前1位减1得5,后面一律为9,得5999
考虑一种情况,n=332,遍历到下标2时发现数字比前一位小,将下标为1处的3改为2,后面置为9后,得329不符合题意,这说明还需要另外加一个循环从下标为1处向前遍历,如果当前位置数字比前一位小了,就把当前位置数字置为9,前一位数字减一,处理后数字变为299
C++: 0ms,59MB
xxxxxxxxxx341class Solution {2public:3 int monotoneIncreasingDigits(int n) 4 {5 string s=to_string(n);6 for(int i=1;i<s.size();++i)7 {8 if(s[i]<s[i-1])9 {10 --s[i-1];11 for(int j=i-1;j>=1;--j)12 {13 if(s[j]<s[j-1])14 {15 s[j]='9';16 --s[j-1];17 }18 else19 break;20 }21 for(int j=i;j<s.size();++j)22 s[j]='9';23 break;24 }25 }26 n=0;27 for(char& ch:s)28 {29 n*=10;30 n+=ch-'0';31 }32 return n;33 }34};方法2:从右往左遍历(大佬的优雅方法)
C++: 4ms,5.9MB
xxxxxxxxxx171class Solution {2public:3 int monotoneIncreasingDigits(int n) 4 {5 string s=to_string(n);6 int flag;7 for(int i=s.size()-1;i>=1;--i)8 if(s[i-1]>s[i])9 {10 flag=i;11 --s[i-1];12 }13 for(int i=flag;i<s.size();++i)14 s[i]='9';15 return stoi(s);16 }17};大佬虽然优雅,但耗时有点长
val: 1->安装监控 2->接受下方节点监控 3->接受上方节点监控
xxxxxxxxxx281class Solution {2public:3 int minCameraCover(TreeNode* root) 4 {5 int ret=0;//摄像头总数6 //采用后序遍历7 function<void(TreeNode*)>dfs=[&](TreeNode* cur)8 {9 if(cur->left!=nullptr)10 dfs(cur->left);11 if(cur->right!=nullptr)12 dfs(cur->right);13 if(cur->left!=nullptr&&cur->left->val==3||cur->right!=nullptr&&cur->right->val==3)//左孩子和右孩子中存在接受上方监控的节点14 {15 cur->val=1;//给当前节点安装监控16 ++ret;17 }18 else if(cur->left!=nullptr&&cur->left->val==1||cur->right!=nullptr&&cur->right->val==1)//左孩子和右孩子中存在装有监控的节点19 cur->val=2;//接受下方节点的监控20 else21 cur->val=3;//接受上方节点的监控22 };23 dfs(root);24 if(root->val==3)//可能出现root节点接受上方节点监控的情况,这时需要给root安装监控25 ++ret;26 return ret;27 }28};本题为边稠密图,更适合普里姆算法
从某一个顶点开始构建生成树,每次将代价最小的新顶点纳入生成树,直到所有顶点都纳入为止
SysuGLM的解释:
Prim 算法是一种用于解决无向图最小生成树问题的贪心算法。它的基本思想是从一个顶点开始,不断地寻找与当前生成树距离最近的顶点,将其加入到生成树中,直到所有顶点都加入到生成树中为止。该算法是由捷克数学家 Vojtěch Jarník 于 1930 年发现的,并在 1957 年由美国计算机科学家 Robert C. Prim 重新发现,因此得名 Prim 算法。 以下是 Prim 算法的基本步骤:
- 初始化一个空的最小生成树 T。
- 任选图中一个顶点 v,将其加入到 T 中。
- 在图中寻找距离 T 最近的顶点 u,将边 (u, v) 加入到 T 中。
- 重复步骤 3,直到所有顶点都加入到 T 中。
- 得到的 T 即为原图的最小生成树。
Prim 算法的时间复杂度取决于具体的实现方式。最简单的实现方式是用邻接矩阵表示图,其时间复杂度为 O(n^2),其中 n 为图的顶点数。使用优先队列和邻接表可以进一步优化算法的性能,将时间复杂度降低到 O(nlogn)。
设总共V个节点,时间复杂度
xxxxxxxxxx381class Solution {2public:3 int minCostConnectPoints(vector<vector<int>>& points)//prim算法4 {5 int n=points.size();//点的总数6 vector<int>isjoin(n);//是否已被连接7 vector<int>lowcost(n);//连入图的最小开销8 lowcost[0]=0;9 isjoin[0]=1;10 for(int i=1;i<n;++i)11 lowcost[i]=abs(points[i][0]-points[0][0])+abs(points[i][1]-points[0][1]);//初始化图,到0节点的最小距离12 int ret=0;13 for(int i=1;i<n;++i)14 {15 int cur_min=INT_MAX;16 int cur_idx;17 for(int j=1;j<n;++j)//寻找当前入图开销最小的节点18 {19 if(isjoin[j]==1)//排除已经入图的节点20 continue;21 if(lowcost[j]<cur_min)22 {23 cur_min=lowcost[j];24 cur_idx=j;25 }26 }27 ret+=cur_min;28 isjoin[cur_idx]=1;29 for(int j=1;j<n;++j)//更新所有节点的入图距离30 {31 if(isjoin[j]==1)32 continue;33 lowcost[j]=min(lowcost[j],abs(points[j][0]-points[cur_idx][0])+abs(points[j][1]-points[cur_idx][1]));34 }35 }36 return ret;37 }38};SysuGLM的解释:
Kruskal 算法是一种贪心算法,用于求解连通网的最小生成树。具体步骤如下:
- 将所有的边按照权重从小到大排序。
- 初始化一个空集合,用于存放已选择的边。
- 按照排序后的顺序依次遍历每条边,检查当前边的两个顶点是否属于同一个连通分量(可以使用并查集数据结构进行快速判断)。如果不属于同一个连通分量,那么将这条边加入到已选择的边的集合中,并合并这两个顶点所在的连通分量;如果已经属于同一个连通分量,那么跳过这条边。
- 当已选择的边的数量等于顶点数减一时,算法结束。此时已选择的边构成了连通网的最小生成树。 这种算法的时间复杂度为 O(ElogE),其中 E 是边的数量。
该算法利用Quick Union版本的并查集, 有关并查集Quick Find和Quick Union版本的区别, 参考本文
xxxxxxxxxx391class Solution {2public:3 int minCostConnectPoints(vector<vector<int>>& points)//Kruskal算法4 {5 int n=points.size();6 vector<pair<int,int>>edge;7 edge.reserve(n*(n-1)/2);8 for(int i=0;i<n;++i)9 for(int j=i+1;j<n;++j)10 edge.emplace_back(make_pair(i,j));11 sort(edge.begin(),edge.end(),[&](pair<int,int>&a,pair<int,int>&b){12 return abs(points[a.first][0]-points[a.second][0])+abs(points[a.first][1]-points[a.second][1])<abs(points[b.first][0]-points[b.second][0])+abs(points[b.first][1]-points[b.second][1]);13 });14 vector<int>bing(n);15 for(int i=0;i<n;++i)16 bing[i]=i;17 function<int(int)>find=[&](int cur)18 {19 if(bing[cur]!=cur)20 return find(bing[cur]);21 else 22 return cur;23 };24 int ret=0;25 for(auto& p:edge)26 {27 int pf=find(p.first);28 int ps=find(p.second);29 if(pf==ps)30 continue;31 else32 {33 ret+=abs(points[p.first][0]-points[p.second][0])+abs(points[p.first][1]-points[p.second][1]);34 bing[pf]=ps;35 }36 }37 return ret;38 }39};最后一个测试用例会超时😭

图出自王道考研数据结构
例题:
BFS算法比较基础,且只能处理不带权的图,这里就不介绍了
当前算法适用于稠密图
求带权图的最短路径长度,局限是不能处理负权图
对于一系列顶点
初始化三个数组:
bool final[n]标记各个顶点是否已经找到最短路径,初始化为Falseint dist[n] 到达各个顶点的最短路径长度,初始化为int path[n] 各个顶点在路径上的前驱,初始化为-1xxxxxxxxxx5112class Solution {3public:4 int networkDelayTime(vector<vector<int>>& times, int n, int k) 5 {6 vector<vector<int>>arr(n+1);//邻接表7 for(int i=1;i<=n;++i)8 arr[i].resize(n+1,inf);//初始化邻接表为无穷大9 for(auto& time:times)10 arr[time[0]][time[1]]=time[2];11 //dijkstra算法12 vector<bool>final(n+1,false);//标记各个顶点是否已经找到最短路径,初始化为false13 vector<int>dist(n+1,inf);//到达各个顶点的最短路径长度14 vector<int>path(n+1,-1);//各个顶点在路径上的前驱,初始化为-1,在本题可有可无15 int cur=k;//cur是当前正在访问的节点16 final[cur]=true;17 int cnt=1;//cnt统计当前已找到最短路径的顶点数量18 dist[k]=0;19 for(;cnt<n;++cnt)20 {21 //计算并更新与当前节点直接相连,并且final值为false的全部节点的dist值22 for(int i=1;i<=n;++i)23 {24 if(final[i]==false&&arr[cur][i]<inf)25 {26 dist[i]=min(dist[i],dist[cur]+arr[cur][i]); 27 }28 }29 //找到从当前节点出发,下一个最近的节点30 int tmp=inf,tmp_idx=-1;31 for(int i=1;i<=n;++i)32 {33 if(final[i]==false)34 {35 if(dist[i]<tmp)36 {37 tmp=dist[i];38 tmp_idx=i;39 }40 }41 }42 if(tmp_idx==-1)43 return -1;//收不到信号的情况44 path[tmp_idx]=cur;45 cur=tmp_idx;//cur指向下一个要访问的节点46 //将下一个节点在final数组对应下标位置的值改为true47 final[cur]=true;48 }49 return *max_element(dist.begin()+1,dist.end());50 }51};leetcode743通过,92ms,36.5MB
复杂度分析
节点总数为
时间复杂度
当前算法只能求一个顶点到其他所有顶点的最短路径,如果需要求所有顶点到其他顶点的最短路径,则需要将该算法循环
当前算法适用于稀疏图
xxxxxxxxxx3512class Solution {3public:4 int networkDelayTime(vector<vector<int>>& times, int n, int k) 5 {6 using Pair=pair<int,int>;7 vector<vector<Pair>>vec(n+1);8 for(auto& time:times)9 {10 vec[time[0]].emplace_back(make_pair(time[1],time[2]));11 }12 priority_queue<Pair,vector<Pair>,greater<>>pq;13 vector<int>dist(n+1,inf);14 pq.emplace(0,k);//分别代表当前最小的dist值,及其对应下标15 dist[k]=0;16 while(!pq.empty())17 {18 auto cur=pq.top();//cur.first是当前处理节点的最小dist值,cur.second是当前处理节点的下标19 pq.pop();20 if(dist[cur.second]<cur.first)21 continue;22 auto& tmp=vec[cur.second];23 for(Pair& pa:tmp)//pa.first是下一个要处理的节点,pa.second是到该节点的距离24 {25 if(dist[pa.first]>cur.first+pa.second)26 {27 dist[pa.first]=cur.first+pa.second;28 pq.emplace(dist[pa.first],pa.first);29 }30 }31 }32 int ret=*max_element(dist.begin()+1,dist.end());33 return ret==inf?-1:ret;34 }35};复杂度分析
设顶点数为
dist数组占用空间
Floyd算法更加通用,可以解决带负权值的图,但前提是最短路径存在
如上图所示,要求A到C的最短路径,如果选择的路径是沿着箭头一直前进,每循环一圈路径长度减2,A到C的路径可以无穷小,不存在最短路径
xxxxxxxxxx3312class Solution {3public:4 int networkDelayTime(vector<vector<int>>& times, int n, int k) //floyd算法5 {6 vector<vector<int>>arr(n+1,vector<int>(n+1,inf));//代表各顶点间的最短路径长度,初始化为邻接表7 for(auto& time:times)8 arr[time[0]][time[1]]=time[2];//不允许在其他节点中转,最短路径是9 vector<vector<int>>path(n+1,vector<int>(n+1,-1));//两个节点之间的中转点10 for(int i=1;i<=n;++i)//依次考虑以第i个节点为中转,更新11 {12 for(int j=1;j<=n;++j)//遍历所有可能的方向13 {14 for(int m=1;m<=n;++m)15 {16 if(arr[j][m]>arr[j][i]+arr[i][m])17 {18 arr[j][m]=arr[j][i]+arr[i][m];19 path[j][m]=i;20 }21 }22 }23 }24 int ret=0;25 for(int i=1;i<=n;++i)26 {27 if(i==k)28 continue;29 ret=max(ret,arr[k][i]);30 }31 return ret==inf?-1:ret;32 }33};leetcode743通过,160ms,37MB
复杂度分析
该过程相当于对一个三维数组的动态规划(在内存使用上可以只使用二维数组),时间复杂度
(引用自百度百科)
贝尔曼-福特算法与迪科斯彻算法类似,都以松弛操作为基础,即估计的最短路径值渐渐地被更加准确的值替代,直至得到最优解。在两个算法中,计算时每个边之间的估计距离值都比真实值大,并且被新找到路径的最小长度替代。 然而,迪科斯彻算法以贪心法选取未被处理的具有最小权值的节点,然后对其的出边进行松弛操作;而贝尔曼-福特算法简单地对所有边进行松弛操作,共
次,其中
是图的点的数量。在重复地计算中,已计算得到正确的距离的边的数量不断增加,直到所有边都计算得到了正确的路径。这样的策略使得贝尔曼-福特算法比迪科斯彻算法适用于更多种类的输入。
xxxxxxxxxx1912class Solution {3public:4 int networkDelayTime(vector<vector<int>>& times, int n, int k) //Bellman-ford算法5 {6 vector<int>dist(n+1,inf);7 dist[k]=0;8 for(int i=0;i<n-1;++i)//循环n-1次,一定能松弛所有顶点,否则没有被松弛的收不到信号9 {10 for(auto& time:times)//遍历所有边11 {12 if(dist[time[0]]+time[2]<dist[time[1]])//松弛操作13 dist[time[1]]=dist[time[0]]+time[2];14 }15 }16 int ret=*max_element(dist.begin()+1,dist.end());17 return ret==inf?-1:ret;18 }19};leetcode743通过,152ms,35.7MB
时间复杂度
SPFA算法是对Bellman-ford算法的优化
shortest path faster algorithm
参考文献CSDN SPFA算法,画图详细解释了该算法,适合小白
xxxxxxxxxx3112class Solution {3public:4 int networkDelayTime(vector<vector<int>>& times, int n, int k) 5 {6 queue<int>que;7 vector<int>dist(n+1,inf);8 que.push(k);9 dist[k]=0;10 using Pair=pair<int,int>;11 vector<vector<Pair>>vec(n+1);//从i节点到vec[i].first有一条长度为vec[i].second的路径12 for(auto& time:times)13 vec[time[0]].emplace_back(time[1],time[2]);14 while(!que.empty())15 {16 int front=que.front();17 que.pop();18 auto& ve=vec[front];19 for(auto& p:ve)20 {21 if(dist[p.first]>dist[front]+p.second)22 {23 dist[p.first]=dist[front]+p.second;24 que.push(p.first);25 }26 }27 }28 int ret=*max_element(dist.begin()+1,dist.end());29 return ret==inf?-1:ret;30 }31};leetcode743通过,84ms,39MB
xxxxxxxxxx4012345using namespace std;67int main()//SPFA算法8{9 int n,m,s;10 cin>>n>>m>>s;11 int u,v,w;12 using Pair=pair<int,int>;13 vector<vector<Pair>> g(n+1);//从i节点到g[i].first有一条长度为g[i].second的路径14 for(int i=0;i<m;++i)15 {16 cin>>u>>v>>w;17 g[u].emplace_back(v,w);18 }19 vector<int> dist(n+1,inf);20 dist[s]=0;21 queue<int> q;22 q.push(s);23 while(!q.empty())24 {25 int front=q.front();26 q.pop();27 for(auto& p:g[front])28 {29 if(dist[p.first]>dist[front]+p.second)30 {31 dist[p.first]=dist[front]+p.second;32 q.push(p.first);33 }34 }35 }36 for(int i=1;i<=n;++i)37 cout<<dist[i]<<" ";38 cout<<endl;39 return 0;40}洛谷P3371 【模板】单源最短路径(弱化版)通过
SPFA的复杂度大约是
,k是每个点的平均进队次数(一般的,k是一个常数,在稀疏图中小于2)。
参考王道考研数据结构
AOV网(Activity On Vertex Network):用顶点表示活动的网
用DAG图(有向无环图)表示一个工程,顶点表示活动,有向边
表示“番茄炒蛋工程”的AOV网
拓扑排序的一种结果:
拓扑排序的实现:
出现回路的情况:
当前所有顶点的入度>0,说明原图存在回路
方法1:BFS
xxxxxxxxxx321class Solution {2public:3 bool canFinish(int numCourses, vector<vector<int>>& prerequisites) 4 {5 vector<vector<int>>vec(numCourses);//vec[i]存储完成课程i之后才能完成的课程6 vector<int>indegree(numCourses);//indegree[i]存储课程i在AOV网中的全部前驱节点7 for(auto& pre:prerequisites)8 {9 vec[pre[1]].emplace_back(pre[0]);10 ++indegree[pre[0]];11 }12 stack<int>sta;//当前所有入度为零的节点下标13 for(int i=0;i<numCourses;++i)14 if(indegree[i]==0)15 sta.push(i);//初始化栈16 int cnt=0;//统计当前已经遍历的节点数量17 while(!sta.empty())18 {19 int cur=sta.top();20 ++cnt;21 sta.pop();22 auto& ve=vec[cur];23 for(int& ve_:ve)24 {25 --indegree[ve_];26 if(indegree[ve_]==0)27 sta.push(ve_);28 }29 }30 return cnt==numCourses;31 }32};方法2:DFS
参考力扣官方题解
xxxxxxxxxx441class Solution {2public:3 bool canFinish(int numCourses, vector<vector<int>>& prerequisites) 4 {5 vector<vector<int>>vec(numCourses);//vec[i]存储完成课程i之后才可以完成的课程6 vector<bool>isvisited(numCourses,false);//记录节点i是否正在被访问7 vector<bool>isInStack(numCourses,false);//记录节点i是否已经入栈8 for(auto& pre:prerequisites)9 {10 vec[pre[1]].emplace_back(pre[0]);//初始化vec数组11 }12 int flag=0;//当flag==1时,说明正在被访问的结果遭到二次访问,说明图中有环,返回空数组13 function<void(int)>dfs=[&](int idx){14 if(flag)15 return;16 isvisited[idx]=true;17 auto& ve=vec[idx];//当前节点直接指向的节点18 for(int& ve_:ve)19 {20 if(!isvisited[ve_])//确保正在被访问的结果没有遭到二次访问21 {22 if(!isInStack[ve_])23 dfs(ve_);24 }25 else26 {27 flag=1;28 return;29 }30 }31 isvisited[idx]=false;32 isInStack[idx]=true;33 };34 for(int i=0;i<numCourses;++i)35 if(!isInStack[i])36 {37 dfs(i);38 if(flag)39 return false;40 }41 return true;42
43 }44};方法1:BFS
xxxxxxxxxx381class Solution {2public:3 vector<int> findOrder(int numCourses, vector<vector<int>>& prerequisites) 4 {5 vector<vector<int>>vec(numCourses);//vec[i]存储完成课程i之后才可以完成的课程6 vector<int>indegree(numCourses);//indegree[i]存储课程i节点的所有入度7 vector<int>ret;//返回的排序数组8 ret.reserve(numCourses);//预留空间9 stack<int>sta;10 for(auto& pre:prerequisites)11 {12 vec[pre[1]].emplace_back(pre[0]);//初始化vec数组13 ++indegree[pre[0]];//初始化indegree数组14 }15 for(int i=0;i<numCourses;++i)16 if(indegree[i]==0)17 sta.push(i);18 int cnt=0;//已经遍历过的节点数量19 while(!sta.empty())20 {21 ++cnt;22 int cur=sta.top();23 sta.pop();24 ret.emplace_back(cur);25 auto& ve=vec[cur];//完成当前课程之后才可以完成的课程26 for(int& ve_:ve)27 {28 --indegree[ve_];29 if(indegree[ve_]==0)30 sta.push(ve_);31 }32 }33 if(cnt==numCourses)34 return ret;35 else36 return vector<int>();37 }38};方法2:DFS
xxxxxxxxxx521class Solution {2public:3 vector<int> findOrder(int numCourses, vector<vector<int>>& prerequisites) 4 {5 vector<vector<int>>vec(numCourses);//vec[i]存储完成课程i之后才可以完成的课程6 vector<bool>isvisited(numCourses,false);//记录节点i是否正在被访问7 vector<bool>isInStack(numCourses,false);//记录节点i是否已经入栈8 stack<int>sta;//存储逆拓扑排序序列9 for(auto& pre:prerequisites)10 {11 vec[pre[1]].emplace_back(pre[0]);//初始化vec数组12 }13 int flag=0;//当flag==1时,说明正在被访问的结果遭到二次访问,说明图中有环,返回空数组14 function<void(int)>dfs=[&](int idx){15 if(flag)16 return;17 isvisited[idx]=true;18 auto& ve=vec[idx];//当前节点直接指向的节点19 for(int& ve_:ve)20 {21 if(!isvisited[ve_])//确保正在被访问的结果没有遭到二次访问22 {23 if(!isInStack[ve_])24 dfs(ve_);25 }26 else27 {28 flag=1;29 return;30 }31 }32 sta.push(idx);33 isvisited[idx]=false;34 isInStack[idx]=true;35 };36 for(int i=0;i<numCourses;++i)37 if(!isInStack[i])38 {39 dfs(i);40 if(flag)41 return vector<int>();42 }43 vector<int>ret;44 ret.reserve(numCourses);45 while(!sta.empty())46 {47 ret.emplace_back(sta.top());48 sta.pop();49 }50 return ret;51 }52};参考灵神的题解
xxxxxxxxxx441class Solution {2public:3 vector<int> countPairs(int n, vector<vector<int>>& edges, vector<int>& queries) 4 {5 vector<int>deg(n);6 unordered_map<int,int>cnt_e;7 for(auto& edge:edges)8 {9 int x=edge[0]-1,y=edge[1]-1;10 if(x>y)11 swap(x,y);12 ++deg[x];13 ++deg[y];14 ++cnt_e[x<<16|y];15 }16 vector<int>sorted_deg=deg;17 vector<int>ans(queries.size());18 sort(sorted_deg.begin(),sorted_deg.end());19 for(int j=0;j<queries.size();++j)20 {21 int q=queries[j];22 int left=0,right=n-1;23 while(left<right)24 {25 if(sorted_deg[left]+sorted_deg[right]>q)26 {27 ans[j]+=right-left;28 --right;29 }30 else31 ++left;32 }33 for(auto& e:cnt_e)34 {35 int x=e.first>>16;36 int y=e.first&0xffff;37 int num=e.second;38 if(deg[x]+deg[y]>q&°[x]+deg[y]-num<=q)39 --ans[j];40 }41 }42 return ans;43 }44};方法1:数学,利用组合数直接计算
C:
xxxxxxxxxx131typedef long long ll;2int uniquePaths(int m, int n)3{4 int a=m+n-2,b=m-1<n-1?m-1:n-1;5 if(b==0)6 return 1;7 ll ret=1;8 for(int i=0;i<b;++i)9 {10 ret=ret*(a-i)/(i+1);11 }12 return ret;13}方法2:动态规划
python:
xxxxxxxxxx121class Solution:2 def uniquePaths(self, m: int, n: int) -> int:3 4 def dfs(x,y):5 if x==1 and y==1:6 return 17 if x==1:8 return dfs(x,y-1)9 if y==1:10 return dfs(x-1,y)11 return dfs(x-1,y)+dfs(x,y-1)12 return dfs(m,n)C:
xxxxxxxxxx311int uniquePathsWithObstacles(int** obstacleGrid, int obstacleGridSize, int* obstacleGridColSize)2{3 if(obstacleGrid[0][0]==1)4 return 0;5 int row=obstacleGridSize;6 int col=obstacleGridColSize[0];7 int** arr=(int**)malloc(sizeof(int*)*(row+1));8 for(int i=0;i<=row;++i)9 {10 arr[i]=(int*)malloc(sizeof(int)*(col+1));11 memset(arr[i],0,(col+1)*sizeof(int));12 }13 arr[1][1]=1;14 for(int i=1;i<=row;++i)15 {16 int j=1;17 if(i==1)18 j=2;19 for(;j<=col;++j)20 {21 if(obstacleGrid[i-1][j-1]==1)22 continue;23 arr[i][j]=arr[i-1][j]+arr[i][j-1];24 }25 }26 int ret=arr[row][col];27 for(int i=0;i<=row;++i)28 free(arr[i]);29 free(arr);30 return ret;31}python:
xxxxxxxxxx141class Solution:2 def uniquePathsWithObstacles(self, obstacleGrid: List[List[int]]) -> int:3 4 def dfs(x,y):5 if obstacleGrid[x-1][y-1]==1:6 return 07 if x==1 and y==1:8 return 19 if x==1:10 return dfs(x,y-1)11 if y==1:12 return dfs(x-1,y)13 return dfs(x-1,y)+dfs(x,y-1)14 return dfs(len(obstacleGrid),len(obstacleGrid[0]))方法1:BFS(广度优先搜索)+记忆化搜索
xxxxxxxxxx431class Solution {2public:3 bool wordBreak(string s, vector<string>& wordDict) 4 {5 unordered_map<int,int>hash;6 queue<int> que;7 int wlen=wordDict.size();8 int slen=s.size();9 que.push(0);10 while(!que.empty())11 {12 int cur=que.front();13 if(cur==slen)14 return true;15 que.pop();16 vector<int>wor(wlen,1);17 int findnum=wlen;18 for(int i=0;cur+i<=slen&&findnum>0;++i)19 {20 for(int j=0;j<wlen;++j)21 {22 if(wor[j]==0)23 continue;24 if(i>=wordDict[j].size())25 {26 if(hash[cur+wordDict[j].size()]==0)27 que.push(cur+wordDict[j].size());28 hash[cur+wordDict[j].size()]=1;29 --findnum;30 wor[j]=0;31 continue;32 }33 if(s[cur+i]!=wordDict[j][i])34 {35 --findnum;36 wor[j]=0;37 }38 }39 }40 }41 return false;42 }43};方法2:完全背包
(出自代码随想录)
单词就是物品,字符串s就是背包,单词能否组成字符串s,就是问物品能不能把背包装满。
拆分时可以重复使用字典中的单词,说明就是一个完全背包!
xxxxxxxxxx201class Solution:2 def wordBreak(self, s: str, wordDict: List[str]) -> bool:3 4 def dp(i,c):5 if c==-1:6 return 17 if i<0:8 return 09 flag=110 le=len(wordDict[i])11 if c<le-1:12 return dp(i-1,c)13 for idx,ch in enumerate(wordDict[i]):14 if s[c-le+1+idx]!=ch:15 flag=016 break17 if flag==1:18 return dp(i-1,c)+dp(len(wordDict)-1,c-le)19 return dp(i-1,c)20 return dp(len(wordDict)-1,len(s)-1)!=0每个节点都有偷和不偷两种选择,用pair对组存储两种情况下的最大收益
如果偷了当前节点,则左右节点都不能偷,只有一种情况
如果不偷当前节点,有四种情况:偷左右节点、偷左不偷右、偷右不偷左、左右都不偷
xxxxxxxxxx211class Solution {2public:3 int rob(TreeNode* root) 4 {5 int ret=0;6 //pair中存储的分别是偷和不偷的最大收益7 function<pair<int,int>(TreeNode*)>dfs=[&](TreeNode* cur)8 {9 if(cur==nullptr)10 return make_pair(0,0);11 auto pl=dfs(cur->left);12 auto pr=dfs(cur->right);13 int steal=cur->val+pl.second+pr.second;14 int noSteal=max(pl.first+pr.second,max(pl.second+pr.first,max(pl.first+pr.first,pl.second+pr.second)));15 ret=max(ret,max(steal,noSteal));16 return make_pair(steal,noSteal);17 };18 dfs(root);19 return ret;20 }21};方法1:贪心
用双指针实现,左指针取最小值,右指针取最大值,差值就是最大利润
C:
xxxxxxxxxx2112int maxProfit(int* prices, int pricesSize)3{4 int min=0,max=0;5 int ret=0;6 for(int i=1;i<pricesSize;++i)7 {8 if(prices[i]<prices[min])9 {10 ret=fmax(ret,prices[max]-prices[min]);11 min=i;12 max=i;13 }14 else if(prices[i]>prices[max])15 {16 max=i;17 ret=fmax(ret,prices[max]-prices[min]);18 }19 }20 return ret;21}方法2:动态规划
维护两个变量,分别是have今天结束后 持有股票的最大利润,notHave今天结束后 不持有股票的最大利润
python:
xxxxxxxxxx101class Solution:2 def maxProfit(self, prices: List[int]) -> int:3 have=-prices[0] # 当前持有股票的最大利润4 notHave=0 # 当前不持有股票的最大利润5 for i in range(1,len(prices)):6 tp1=max(have,-prices[i])7 tp2=max(notHave,have+prices[i])8 have=tp19 notHave=tp210 return notHave详见贪心章节
总结一下32题和34题的动态规划区别
32题的特点是只能买一次:
34题的特点是无限次购买:
除了标黄的部分,两题的递推公式都是一样的
对比代码:
32题:
tp1=max(have,-prices[i])
tp2=max(notHave,have+prices[i])
34题:
tp1=max(have,notHave-prices[i])
tp2=max(notHave,have+prices[i])
本题是下一题的削减版,对应下一题的k=2情况
动态规划:
注意,如果你用的是C++,-inf不能简单地用INT_MIN代替,因为动态规划过程中可能会涉及到对INT_MAX减去一个正数的操作
| 3 | 3 | 5 | 0 | 0 | 3 | 1 | 4 | ||
|---|---|---|---|---|---|---|---|---|---|
| 0 | 第一次持有 | -3 | -3 | -3 | 0 | 0 | 0 | 0 | 0 |
| 1 | 第一次卖出 | -inf | 0 | 2 | 2 | 2 | 3 | 3 | 4 |
| 2 | 第二次持有 | -inf | -inf | -5 | 2 | 2 | 2 | 2 | 2 |
| 3 | 第二次卖出 | -inf | -inf | -inf | -5 | 2 | 5 | 5 | 6 |
xxxxxxxxxx51dp[i][0]=max{dp[i-1][0],-prices[i]}2dp[i][1]=max{dp[i-1][1],dp[i-1][0]+prices[i]}3dp[i][2]=max{dp[i-1][2],dp[i-1][1]-prices[i]}4dp[i][3]=max{dp[i-1][3],dp[i-1][2]+prices[i]}5......
python:
xxxxxxxxxx241class Solution:2 def maxProfit(self, prices: List[int]) -> int:3 k=2 # 最多完成k笔交易4 n=len(prices)5 # 构造数组6 dp=[[0]]*n7 for i in range(n):8 dp[i]=[0]*(2*k)9 # 数组初始化第一行10 dp[0][0]=-prices[0]11 for i in range(1,2*k):12 dp[0][i]=-inf13 # 开始递推14 for i in range(1,n):15 dp[i][0]=max(dp[i-1][0],-prices[i]) #第1列的递推16 for j in range(1,2*k):17 if j%2==0: # 偶数列,表示第j//2次持有18 dp[i][j]=max(dp[i-1][j],dp[i-1][j-1]-prices[i])19 else: # 奇数列,表示第j//2+1次卖出20 dp[i][j]=max(dp[i-1][j],dp[i-1][j-1]+prices[i])21 ret=022 for i in range(2*k):23 ret=max(ret,dp[n-1][i])24 return retC++: 实现上有些区别,比如将每次持有和卖出的两种情况压缩到对组内
xxxxxxxxxx371class Solution {2public:3 int maxProfit(vector<int>& prices) 4 {5 using ll=long long;6 int k=2;7 if(prices.size()==0)8 return 0;9 vector<vector<pair<ll,ll>>> dfs(prices.size());10 for(auto&vec:dfs)11 vec.resize(k+1);12 for(auto& pa:dfs[0])13 {14 pa.first=INT_MIN;15 pa.second=INT_MIN;16 }17 dfs[0][0].first=0;18 dfs[0][1].second=-prices[0];19 for(int i=1;i<prices.size();++i)20 {21 for(int j=0;j<=k;++j)22 {23 dfs[i][j].first=max(dfs[i-1][j].first,dfs[i-1][j].second+prices[i]);24 if(j==0)25 dfs[i][j].second=dfs[i-1][j].second;26 else27 dfs[i][j].second=max(dfs[i-1][j].second,dfs[i-1][j-1].first-prices[i]);28 }29 }30 ll ret=0;31 for(int i=0;i<=k;++i)32 {33 ret=max(ret,dfs[prices.size()-1][i].first);34 }35 return ret;36 }37};解析见上一题
python:
xxxxxxxxxx231class Solution:2 def maxProfit(self, k: int, prices: List[int]) -> int:3 n=len(prices)4 # 构造数组5 dp=[[0]]*n6 for i in range(n):7 dp[i]=[0]*(2*k)8 # 数组初始化第一行9 dp[0][0]=-prices[0]10 for i in range(1,2*k):11 dp[0][i]=-inf12 # 开始递推13 for i in range(1,n):14 dp[i][0]=max(dp[i-1][0],-prices[i]) #第1列的递推15 for j in range(1,2*k):16 if j%2==0: # 偶数列,表示第j//2次持有17 dp[i][j]=max(dp[i-1][j],dp[i-1][j-1]-prices[i])18 else: # 奇数列,表示第j//2+1次卖出19 dp[i][j]=max(dp[i-1][j],dp[i-1][j-1]+prices[i])20 ret=021 for i in range(2*k):22 ret=max(ret,dp[n-1][i])23 return retC++:
xxxxxxxxxx361using ll=long long;2class Solution {3public:4 int maxProfit(int k, vector<int>& prices) 5 {6 if(prices.size()==0||k==0)7 return 0;8 vector<vector<pair<ll,ll>>> dfs(prices.size());9 for(auto&vec:dfs)10 vec.resize(k+1);11 for(auto& pa:dfs[0])12 {13 pa.first=INT_MIN;14 pa.second=INT_MIN;15 }16 dfs[0][0].first=0;17 dfs[0][1].second=-prices[0];18 for(int i=1;i<prices.size();++i)19 {20 for(int j=0;j<=k;++j)21 {22 dfs[i][j].first=max(dfs[i-1][j].first,dfs[i-1][j].second+prices[i]);23 if(j==0)24 dfs[i][j].second=dfs[i-1][j].second;25 else26 dfs[i][j].second=max(dfs[i-1][j].second,dfs[i-1][j-1].first-prices[i]);27 }28 }29 ll ret=0;30 for(int i=0;i<=k;++i)31 {32 ret=max(ret,dfs[prices.size()-1][i].first);33 }34 return ret;35 }36};方法1:划分出三种状态
| 1 | 2 | 3 | 0 | 2 | ||
|---|---|---|---|---|---|---|
| 0 | 持有股票 | -1 | -1 | -1 | 1 | 1 |
| 1 | 保持卖出股票 | 0 | 0 | 1 | 2 | 2 |
| 2 | 卖出股票 | -inf | 1 | 2 | -1 | 3 |
xxxxxxxxxx31dp[i][0]=max{dp[i-1][0],dp[i-1][1]-prices[i]}2dp[i][1]=max{dp[i-1][1],dp[i-1][2]}3dp[i][2]=dp[i-1][0]+prices[i]
python:
xxxxxxxxxx151class Solution:2 def maxProfit(self, prices: List[int]) -> int:3 n=len(prices)4 # 构造dp数组5 dp=[[0]*3 for _ in range(n)]6 # 初始化第一行7 dp[0][0]=-prices[0]8 dp[0][1]=09 dp[0][2]=-inf10 for i in range(1,n):11 dp[i][0]=max(dp[i-1][0],dp[i-1][1]-prices[i])12 dp[i][1]=max(dp[i-1][1],dp[i-1][2])13 dp[i][2]=dp[i-1][0]+prices[i]14 ret=max(dp[n-1][1],dp[n-1][2])15 return 0 if ret<0 else ret方法2:两种状态(带下划线的初始化要特殊考虑)
| 1 | 2 | 3 | 0 | 2 | ||
|---|---|---|---|---|---|---|
| 0 | 不持有股票 | 0 | 1 | 2 | 2 | 3 |
| 1 | 持有股票 | -1 | -1 | -1 | 1 | 1 |
xxxxxxxxxx21dp[i][0]=max{dp[i-1][0],dp[i-1][1]+prices[i]}2dp[i][1]=max{dp[i-1][1],dp[i-2][0]-prices[i]}
python:记忆化递归
xxxxxxxxxx101class Solution:2 def maxProfit(self, prices: List[int]) -> int:3 4 def dfs(i,hold):5 if i<0:6 return -inf if hold else 07 if hold:8 return max(dfs(i-1,True),dfs(i-2,False)-prices[i])9 return max(dfs(i-1,False),dfs(i-1,True)+prices[i])10 return dfs(len(prices)-1,False)C++:
xxxxxxxxxx201class Solution {2public:3 int maxProfit(vector<int>& prices) 4 {5 int len=prices.size();6 if(len<=1)7 return 0;8 vector<pair<int,int>>dfs(len);9 dfs[0].first=0;10 dfs[0].second=-prices[0];11 dfs[1].second=max(-prices[1],dfs[0].second);12 dfs[1].first=max(0,dfs[0].second+prices[1]);13 for(int i=2;i<len;++i)14 {15 dfs[i].first=max(dfs[i-1].first,dfs[i-1].second+prices[i]);16 dfs[i].second=max(dfs[i-1].second,dfs[i-2].first-prices[i]);17 }18 return dfs[len-1].first;19 }20};fee=2
| 1 | 3 | 2 | 8 | 4 | 9 | ||
|---|---|---|---|---|---|---|---|
| 0 | 不持有股票 | 0 | 0 | 0 | 5 | 5 | 8 |
| 1 | 持有股票 | -3 | -3 | -3 | -3 | -1 | -1 |
xxxxxxxxxx21dp[i][0]=max{dp[i-1][0],dp[i-1][1]+prices[i]}2dp[i][1]=max{dp[i-1][1],dp[i-1][0]-prices[i]-fee}
python:递归
xxxxxxxxxx101class Solution:2 def maxProfit(self, prices: List[int], fee: int) -> int:3 4 def dfs(i,hold):5 if i<0:6 return -inf if hold else 07 if hold:8 return max(dfs(i-1,True),dfs(i-1,False)-prices[i]-fee)9 return max(dfs(i-1,False),dfs(i-1,True)+prices[i])10 return dfs(len(prices)-1,False)C++:递推
xxxxxxxxxx161class Solution {2public:3 int maxProfit(vector<int>& prices, int fee) 4 {5 int len=prices.size();6 vector<pair<int,int>> dfs(len);7 dfs[0].first=0;8 dfs[0].second=-prices[0]-fee;9 for(int i=1;i<len;++i)10 {11 dfs[i].first=max(dfs[i-1].first,dfs[i-1].second+prices[i]);12 dfs[i].second=max(dfs[i-1].second,dfs[i-1].first-fee-prices[i]);13 }14 return dfs[len-1].first;15 }16};n为nums数组长度
方法1:动态规划
dp[i]表示以i为结尾的最长子序列
时间复杂度
xxxxxxxxxx221class Solution {2public:3 int lengthOfLIS(vector<int>& nums) 4 {5 int len=nums.size();6 vector<int> dp(len,1);7 int ret=1;8 for(int i=1;i<len;++i)9 {10 int tmp=0;11 for(int j=0;j<i;++j)12 {13 if(nums[j]<nums[i])14 tmp=max(tmp,dp[j]);15 }16 if(tmp>0)17 dp[i]=tmp+1;18 ret=max(ret,dp[i]);19 }20 return ret;21 }22};方法2:贪心+二分查找
g[i]为长度为i+1的子序列末尾元素的最小值
贪心+二分查找,时间复杂度
g数组性质:1、严格递增 2、只更新一个位置,更新的位置是第一个>=nums[i]的数的下标
xxxxxxxxxx171class Solution {2public:3 int lengthOfLIS(vector<int>& nums) 4 {5 int len=nums.size();6 vector<int>greed={nums[0]};7 for(int i=1;i<len;++i)8 {9 auto it=lower_bound(greed.begin(),greed.end(),nums[i]);10 if(it==greed.end())11 greed.emplace_back(nums[i]);12 else13 *it=nums[i];14 }15 return greed.size();16 }17};简单题,大佬们可以跳过
xxxxxxxxxx121class Solution:2 def findLengthOfLCIS(self, nums: List[int]) -> int:3 n=len(nums)4 ret=15 tmp=16 for i in range(1,n):7 if nums[i]>nums[i-1]:8 tmp+=19 ret=max(ret,tmp)10 else:11 tmp=112 return retxxxxxxxxxx121class Solution:2 def findLength(self, nums1: List[int], nums2: List[int]) -> int:3 n1=len(nums1)4 n2=len(nums2)5 dp=[[0]*(n2+1) for _ in range(n1+1)]6 ret=07 for i in range(1,n1+1):8 for j in range(1,n2+1):9 if nums1[i-1]==nums2[j-1]:10 dp[i][j]=dp[i-1][j-1]+111 ret=max(ret,dp[i][j])12 return ret| 10 | 5 | 2 | 1 | 5 | 2 | |
|---|---|---|---|---|---|---|
| 2 | 0 | 0 | 1 | 1 | 1 | 1 |
| 5 | 0 | 1 | 1 | 1 | 2 | 2 |
| 1 | 0 | 1 | 1 | 2 | 2 | 2 |
| 2 | 0 | 1 | 2 | 2 | 2 | 3 |
| 5 | 0 | 1 | 2 | 2 | 3 | 3 |
python:
xxxxxxxxxx101class Solution:2 def maxUncrossedLines(self, nums1: List[int], nums2: List[int]) -> int:3 4 def dp(i,j):5 if i<0 or j<0:6 return 07 if nums1[i]==nums2[j]:8 return dp(i-1,j-1)+19 return max(dp(i-1,j),dp(i,j-1))10 return dp(len(nums1)-1,len(nums2)-1)代码随想录:
dp[i]:包括下标i(以nums[i]为结尾)的最大连续子序列和为dp[i]。
- 确定递推公式
dp[i]只有两个方向可以推出来:
- dp[i - 1] + nums[i],即:nums[i]加入当前连续子序列和
- nums[i],即:从头开始计算当前连续子序列和
一定是取最大的,所以dp[i] = max(dp[i - 1] + nums[i], nums[i]);
C++
xxxxxxxxxx131class Solution {2public:3 int maxSubArray(vector<int>& nums) 4 {5 int ret=nums[0],add=nums[0];6 for(int i=1;i<nums.size();++i)7 {8 add=max(add+nums[i],nums[i]);9 ret=max(ret,add);10 }11 return ret;12 }13};python
xxxxxxxxxx81class Solution:2 def maxSubArray(self, nums: List[int]) -> int:3 add=04 ret=-1000005 for num in nums:6 add=max(add+num,num)7 ret=max(ret,add)8 return ret本题和45:不相交的线很像
xxxxxxxxxx101class Solution:2 def isSubsequence(self, s: str, t: str) -> bool:3 4 def dp(i,j):5 if i<0 or j<0:6 return 07 if s[i]==t[j]:8 return dp(i-1,j-1)+19 return max(dp(i-1,j),dp(i,j-1))10 return dp(len(s)-1,len(t)-1)==len(s)dp(i,j)表示 字符串t的前i+1个字母(t[0:i+1]) 在 字符串s的前j+1个字母(s[0:j+1])的子序列中 出现的次数
| dp(i,j) | s[j] | b | a | b | g | b | a | g |
|---|---|---|---|---|---|---|---|---|
| t[i] | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
| b | 0 | 1 | 1 | 2 | 2 | 3 | 3 | 3 |
| a | 0 | 0 | 1 | 1 | 1 | 1 | 4 | 4 |
| g | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 5 |
解析:
当t[i]!=s[j]时,当前的两个字符不匹配,dp(i,j)=dp(i,j-1),t[0:i+1]和s[0:j+1]的匹配问题可以转化为t[0:i+1]和s[0:j]的匹配问题。
举个例子,s=“bab”和t=“ba”不同子序列数,等价于s=“ba”和t=“ba”的不同子序列数,因为前者两个串末尾不同,可以看作s1新增的末尾字母b对不同子序列数不构成影响
当t[i]==s[j]时,当前的两个字符匹配,dp(i,j)=dp(i,j-1)+dp(i-1,j-1)。
举个例子,s=“babgba”和t=“ba”的不同子序列数,等于s=“babgb”和g=“ba”的子序列数,加上s=“babgb”,t=“b”的子序列数。
python:(记忆化递归)
xxxxxxxxxx121class Solution:2 def numDistinct(self, s: str, t: str) -> int: # 记忆化递归dp3 4 def dp(i,j):5 if i<0:6 return 17 if j<0:8 return 09 if t[i]==s[j]:10 return dp(i,j-1)+dp(i-1,j-1)11 return dp(i,j-1)12 return dp(len(t)-1,len(s)-1)C++
xxxxxxxxxx211class Solution {2public:3 int numDistinct(string s, string t) //递推版dp4 {5 using ll=unsigned long long;6 int slen=s.size(),tlen=t.size();7 //初始化二维数组8 vector<vector<ll>>dp(tlen+1);9 dp[0].resize(slen+1,1);10 for(int i=1;i<=tlen;++i)11 dp[i].resize(slen+1);12 //递推13 for(int i=1;i<=tlen;++i)14 for(int j=1;j<=slen;++j)15 if(t[i-1]==s[j-1])16 dp[i][j]=dp[i][j-1]+dp[i-1][j-1];17 else18 dp[i][j]=dp[i][j-1];19 return dp[tlen][slen];20 }21};Javascript
xxxxxxxxxx241/**2 * @param {string} s3 * @param {string} t4 * @return {number}5 */6var numDistinct = function(s, t) //递推版dp7{8 let dp=new Array();9 for(let i=0;i<=t.length;++i)10 dp[i]=new Array();11 for(let i=0;i<=s.length;++i)12 dp[0][i]=1;13 for(let i=1;i<=t.length;++i)14 dp[i][0]=0;15 for(let i=1;i<=t.length;++i)16 for(let j=1;j<=s.length;++j)17 {18 if(t[i-1]==s[j-1])19 dp[i][j]=dp[i][j-1]+dp[i-1][j-1];20 else21 dp[i][j]=dp[i][j-1];22 }23 return dp[t.length][s.length];24};这题本质上和动态规划43:最长公共子序列相同
python:
xxxxxxxxxx101class Solution:2 def minDistance(self, word1: str, word2: str) -> int:3 4 def dp(i,j):5 if i<0 or j<0:6 return 07 if word1[i]==word2[j]:8 return dp(i-1,j-1)+19 return max(dp(i-1,j),dp(i,j-1))10 return len(word1)+len(word2)-2*dp(len(word1)-1,len(word2)-1)C
xxxxxxxxxx3512int longestCommonSubsequence(char * text1, char * text2)3{4 char s1[1005]=" ",s2[1005]=" ";5 strcat(s1,text1);6 strcat(s2,text2);7 int l1=strlen(text1);8 int l2=strlen(text2);9 int** mat=(int**)malloc((l1+1)*sizeof(int*));10 for(int i=0;i<=l1;++i)11 mat[i]=(int*)malloc((l2+1)*sizeof(int));12 for(int i=0;i<=l1;++i)13 mat[i][0]=0;14 for(int i=0;i<=l2;++i)15 mat[0][i]=0;16 for(int i=1;i<=l1;++i)17 {18 for(int j=1;j<=l2;++j)19 {20 if(s1[i]==s2[j])21 mat[i][j]=mat[i-1][j-1]+1;22 else23 mat[i][j]=max(mat[i-1][j],mat[i][j-1]);24 }25 }26 int ret=mat[l1][l2];27 for(int i=0;i<=l1;++i)28 free(mat[i]);29 free(mat);30 return ret;31}32int minDistance(char * word1, char * word2)33{34 return strlen(word1)+strlen(word2)-2*longestCommonSubsequence(word1,word2);35}中心扩散解法:时间复杂度
xxxxxxxxxx351class Solution {2public:3 int countSubstrings(string s) 4 {5 int n=s.size();6 int ret=n;7 for(int i=1;i<n-1;++i)8 {9 int left=i-1,right=i+1;10 while(left>=0&&right<n)11 {12 if(s[left]==s[right])13 ++ret;14 else15 break;16 --left;17 ++right;18 }19 }20 for(int i=0;i<n-1;++i)21 {22 int left=i,right=i+1;23 while(left>=0&&right<n)24 {25 if(s[left]==s[right])26 ++ret;27 else28 break;29 --left;30 ++right;31 }32 }33 return ret;34 }35};动态规划解法也是
dp(i,j)表示在区间[i,j]内最长回文子序列的长度
xxxxxxxxxx121class Solution:2 def longestPalindromeSubseq(self, s: str) -> int:3 4 def dp(i,j):5 if i==j:6 return 17 if i>j:8 return 09 if s[i]==s[j]:10 return dp(i+1,j-1)+211 return max(dp(i,j-1),dp(i+1,j))12 return dp(0,len(s)-1)考察二维差分和三维动态规划
此题定义了pi数组,pi[i][j]意义为pizza数组中左上角(i,j)到右下角(row-1,col-1)矩形区域内苹果总数
dp(i,j,c)的意义为左上角(i,j)到右下角(row-1,col-1)矩形区域切c刀的方案总数
xxxxxxxxxx361class Solution:2 def ways(self, pizza: List[str], k: int) -> int:3 mod=10**9+74 row=len(pizza)5 col=len(pizza[0])6 pi=[[0]*col for _ in range(row)]7 if pizza[row-1][col-1]=="A":8 pi[row-1][col-1]=19 for i in range(row-2,-1,-1):10 pi[i][col-1]=pi[i+1][col-1]11 if pizza[i][col-1]=="A":12 pi[i][col-1]+=113 for i in range(col-2,-1,-1):14 pi[row-1][i]=pi[row-1][i+1]15 if pizza[row-1][i]=="A":16 pi[row-1][i]+=117 for i in range(row-2,-1,-1):18 for j in range(col-2,-1,-1):19 pi[i][j]=pi[i+1][j]+pi[i][j+1]-pi[i+1][j+1]20 if pizza[i][j]=="A":21 pi[i][j]+=122 23 def dp(i,j,c):24 if c==0:25 return 1 if pi[i][j]>0 else 026 tmp=027 for i1 in range(i+1,row):28 if pi[i][j]-pi[i1][j]!=0 and pi[i1][j]!=0:29 tmp+=dp(i1,j,c-1)30 tmp%=mod31 for j1 in range(j+1,col):32 if pi[i][j]-pi[i][j1]!=0 and pi[i][j1]!=0:33 tmp+=dp(i,j1,c-1)34 tmp%=mod35 return tmp36 return dp(0,0,k-1)%mod动态规划入门:从记忆化搜索到递推【基础算法精讲 17】(参考视频)
维护一个数组vec[i]表示从前i个房子中能获得的最大金额和
vec[i]=max(vec[i-2]+nums[i],vec[i-1])
如果选择偷当前第i间的,最优收益是偷前i-2间的收益加上本间的收益
如果不偷当前第i间,最优收益是偷前i-1间的收益
C++:
xxxxxxxxxx211class Solution {2public:3 int rob(vector<int>& nums) 4 {5 vector<int>vec(nums.size());6 //先处理边界情况,确保nums.size()>27 if(nums.size()==1)8 return nums[0];9 else if(nums.size()==2)10 return max(nums[0],nums[1]);11 vec[0]=nums[0];12 vec[1]=max(nums[0],nums[1]);13 int ret=0;//维护vec[]数组中的最大值14 for(int i=2;i<nums.size();++i)15 {16 vec[i]=max(vec[i-1],vec[i-2]+nums[i]);17 ret=max(ret,vec[i]);18 }19 return ret;20 }21};Python:
xxxxxxxxxx151class Solution:2 def rob(self, nums: List[int]) -> int:3 li=[]4 le=len(nums)5 if le==1:6 return nums[0]7 elif le==2:8 return max(nums[0],nums[1])9 li.append(nums[0])10 li.append(max(nums[0],nums[1]))11 i=212 while i<le:13 li.append(max(li[i-1],li[i-2]+nums[i]))14 i+=115 return li[le-1](灵神的递归做法)
xxxxxxxxxx91class Solution: # 递归做法2 def rob(self, nums: List[int]) -> int:3 @(cache)4 def dfs(idx):5 if idx<0:6 return 07 cur=max(dfs(idx-1),dfs(idx-2)+nums[idx])8 return cur9 return dfs(len(nums)-1)JavaScript:
xxxxxxxxxx151/**2 * @param {number[]} nums3 * @return {number}4 */5var rob = function(nums) 6{7 if(nums.length==1)8 return nums[0];9 let dp=new Array();10 dp[0]=nums[0];11 dp[1]=Math.max(nums[0],nums[1]);12 for(let i=2;i<nums.length;++i)13 dp[i]=Math.max(dp[i-1],dp[i-2]+nums[i]);14 return Math.max(dp[nums.length-1],dp[nums.length-2]);15};课后作业:
用vec[i]表示到达第i级楼梯至少需要几步
一次可以跨1或2阶,故vec[i]=vec[i-1]+vec[i-2]
C:
xxxxxxxxxx271int a[46];2int digui(int n)3{4 if(a[n]!=0)5 return a[n];6 else7 {8 a[n]=digui(n-1)+digui(n-2);9 return a[n];10 }11}12int climbStairs(int n)13{14 a[1]=1;15 a[2]=2;16 if(n==1) 17 {18 //a[1]=1;19 return 1;20 }21 if(n==2) 22 {23 //a[2]=2;24 return 2;25 }26 return digui(n);27}python:
xxxxxxxxxx101class Solution: # 等价于斐波那契数列2 def climbStairs(self, n: int) -> int:3 4 def dfs(i):5 if i==1:6 return 17 elif i==2:8 return 29 return dfs(i-1)+dfs(i-2)10 return dfs(n)用数组li[k]表示到达第k级的最小花费
因为出发没有花费,li[0]=li[1]=0
li[k]=min(li[k-1]+cost[k-1],li[k-2]+cost[k-2])
python:
xxxxxxxxxx81class Solution:2 def minCostClimbingStairs(self, cost: List[int]) -> int:3 i=04 le=len(cost)5 li=[0]*(le+1)6 for k in range(2,le+1):7 li[k]=min(li[k-1]+cost[k-1],li[k-2]+cost[k-2])8 return li[le]dfs[i]表示长度为i的字符串的好字符串数目
dfs[0]=1,dfs[k]=0(k<0)
dfs[i]=dfs[i-zero]+dfs[i-one]
为了C++防溢出(python防爆内存),需要在计算过程中对
C++:
xxxxxxxxxx281using ll=long long;2class Solution {3public:4 int countGoodStrings(int low, int high, int zero, int one) 5 {6 ll m=1000000007;7 vector<ll>dfs(high+1);8 for(int i=1;i<=high;++i)9 {10 if(i-zero==0)11 dfs[i]+=1;12 else if(i-zero>0)13 dfs[i]+=dfs[i-zero];14 if(i-one==0)15 dfs[i]+=1;16 else if(i-one>0)17 dfs[i]+=dfs[i-one];18 dfs[i]%=m; 19 }20 ll ret=0;21 for(int i=low;i<=high;++i)22 {23 ret+=dfs[i];24 ret%=m;25 }26 return ret;27 }28};python:
xxxxxxxxxx151m=10**9+72class Solution:3 def countGoodStrings(self, low: int, high: int, zero: int, one: int) -> int:4 5 def dfs(i):6 if i<0:7 return 08 elif i==0:9 return 110 return dfs(i-zero)%m+dfs(i-one)%m11 ret=012 for k in range(low,high+1):13 ret+=dfs(k)14 ret=ret%m15 return ret%(10**9+7)本题和打家劫舍类似,可以套用上次的代码,因为首尾相接,从[0,n]间房获得的最大收益等价于
max{从[0,n-1]间房获得的最大收益,从[1,n]间房获得的最大收益}
C:
xxxxxxxxxx301int rob1(int* nums, int numsSize)2{3 int first=0,second=0,max=0;4 for(int i=0;i<numsSize;++i)5 {6 if(i>=2)7 {8 int this=first+nums[i]>second?first+nums[i]:second;9 first=second;10 second=this;11 }12 else13 {14 if(i==0)15 first=nums[0];16 else17 second=nums[1]>nums[0]?nums[1]:nums[0];18 }19 }20 return first>second?first:second;21}22
23int rob(int* nums, int numsSize)24{25 if(numsSize==1)26 return nums[0];27 int ans1=rob1(nums,numsSize-1);28 int ans2=rob1(nums+1,numsSize-1);29 return ans1>ans2?ans1:ans2;30}python:
xxxxxxxxxx181class Solution:2 def rob(self, nums: List[int]) -> int:3 le=len(nums)4 if(le==1):5 return nums[0]6 n1=nums[0:le-1]7 n2=nums[1:le]8 9 def dfs1(i):10 if i<0:11 return 012 return max(dfs1(i-1),dfs1(i-2)+n1[i])13 14 def dfs2(i):15 if i<0:16 return 017 return max(dfs2(i-1),dfs2(i-2)+n2[i])18 return max(dfs1(le-2),dfs2(le-2))Javascript:
xxxxxxxxxx261/**2 * @param {number[]} nums3 * @return {number}4 */5var rob1 = function(nums) 6{7 if(nums.length==1)8 return nums[0];9 let dp=new Array();10 dp[0]=nums[0];11 dp[1]=Math.max(nums[0],nums[1]);12 for(let i=2;i<nums.length;++i)13 dp[i]=Math.max(dp[i-1],dp[i-2]+nums[i]);14 return Math.max(dp[nums.length-1],dp[nums.length-2]);15};16var rob = function(nums) 17{18 if(nums.length==1)19 return nums[0];20 var back=nums.pop();21 var ret1=rob1(nums);22 nums.push(back);23 nums.shift();24 var ret2=rob1(nums);25 return Math.max(ret1,ret2);26};解法1:动态规划
定义dp[i]是整数i拆分后相乘能得到的最大整数(i>=2)
dp[i]=max(j*(i-j),j*dp[i-j]) (1<=j<i)
xxxxxxxxxx171class Solution {2public:3 int integerBreak(int n) 4 {5 vector<int>dp(60,0);6 dp[1]=1;7 dp[2]=1;8 for(int i=3;i<=n;++i)9 {10 for(int j=1;j<=i/2;++j)11 {12 dp[i]=max(dp[i],max(j*(i-j),j*dp[i-j]));13 }14 }15 return dp[n];16 }17};解法2: 数学
粘贴自讨论区:
If an optimal product contains a factorf >= 4, then you can replace it with factors2and f-2 without losing optimality, as 2*(f-2) = 2f-4 >= f. So you never need a factor greater than or equal to 4, meaning you only need factors 1, 2 and 3 (and 1 is of course wasteful and you'd only use it for n=2 and n=3, where it's needed).
For the rest I agree, 3*3 is simply better than2*2*2, so you'd never use 2more than twice.
C:
xxxxxxxxxx191int integerBreak(int n)2{3 switch(n)4 {5 case 2:return 1;6 case 3:return 2;7 case 4:return 4;8 }9 int a=n/3;10 int b=n%3;11 int ret=0;12 if(b==2)13 ret=pow(3,a)*2;14 else if(b==1)15 ret=pow(3,a-1)*4;16 else17 ret=pow(3,a);18 return ret;19}C++: 数组动规
xxxxxxxxxx181class Solution {2public:3 int numTrees(int n) 4 {5 vector<int>dp(20,0);6 dp[0]=1;7 dp[1]=1;8 for(int i=2;i<=n;++i)9 {10 for(int j=0;j<i/2;++j)11 dp[i]+=dp[i-j-1]*dp[j];12 dp[i]*=2;13 if(i%2!=0)14 dp[i]+=dp[i/2]*dp[i/2];15 }16 return dp[n];17 }18};python: 记忆化递归
xxxxxxxxxx111class Solution:2 def numTrees(self, n: int) -> int:3 4 def dp(idx):5 if idx==0:6 return 17 tmp=08 for i in range(0,idx):9 tmp+=dp(i)*dp(idx-1-i)10 return tmp11 return dp(n)01背包:416. 分割等和子集 474. 一和零 494. 目标和 879. 盈利计划 1049. 最后一块石头的重量 II 1230. 抛掷硬币
完全背包:1449. 数位成本和为目标值的最大数字 322. 零钱兑换 518. 零钱兑换 II 279. 完全平方数
0-1背包 完全背包 基础算法精讲 18(视频链接)
C++:
xxxxxxxxxx281class Solution {2public:3 int findTargetSumWays(vector<int>& nums, int target) 4 {5 int cnt=0,add=0,left=0;6 left=accumulate(nums.begin(),nums.end(),0);7 function<void(int idx)>dfs=[&](int idx)8 {9 if(abs(target-add)>left)10 return;11 if(idx==nums.size())12 {13 if(add==target)14 ++cnt;15 return;16 }17 add+=nums[idx];18 left-=nums[idx];19 dfs(idx+1);20 add-=2*nums[idx];21 dfs(idx+1);22 add+=nums[idx];23 left+=nums[idx];24 };25 dfs(0);26 return cnt;27 }28};示例出自CSDN
有n个物品,它们有各自的体积和价值,现有给定容量的背包,如何让背包里装入的物品具有最大的价值总和?
为方便讲解和理解,下面讲述的例子均先用具体的数字代入,即:eg:number=4,capacity=8
| i(物品编号) | 1 | 2 | 3 | 4 |
|---|---|---|---|---|
| w(体积) | 2 | 3 | 4 | 5 |
| v(价值) | 3 | 4 | 5 | 6 |
上述例子的dp数组打印: (dfs(i,c)=max(dfs(i-1,c),dfs(i-1,c-w[i])+v[i]))
| dfs | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
|---|---|---|---|---|---|---|---|---|---|
| -1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 0 | 0 | 0 | 3 | 3 | 3 | 3 | 3 | 3 | 3 |
| 1 | 0 | 0 | 3 | 4 | 4 | 7 | 7 | 7 | 7 |
| 2 | 0 | 0 | 3 | 4 | 5 | 7 | 8 | 9 | 9 |
| 3 | 0 | 0 | 3 | 4 | 5 | 7 | 8 | 9 | 10 |

灵神0-1背包递归模板(python):
xxxxxxxxxx281from functools import cache2
3
4def zero_one_knapsack(capacity: int, w: list[int], v: list[int]):5 """6 灵神0-1背包模板7 :param capacity: 背包容量8 :param w: 物品重量9 :param v: 物品价值10 :return: 取物品的最大价值11 """12 n = len(w)13
14 15 def dfs(i, c):16 """17 深度优先搜索18 :param i: 只考虑前i件物品19 :param c: 剩余容量为c20 :return: 能获得的最大价值21 """22 if i < 0:23 return 024 if c - w[i] < 0:25 return dfs(i - 1, c)26 return max(dfs(i - 1, c), dfs(i - 1, c - w[i]) + v[i])27
28 return dfs(n - 1, capacity)上述模板的C++版本:
xxxxxxxxxx33123456using namespace std;7int zero_one_knapsack(int capacity,vector<int>&w,vector<int>&v)8{9 unordered_map<string,int>cache;//用于实现记忆化递归的哈希函数10 function<int(int,int)>dfs;11 function<int(int,int)>cdfs=[&](int i,int c)//直接可以调用,带有记忆化效果12 {13 string key=to_string(i)+string(",")+to_string(c);14 if(cache.find(key)==cache.end())15 cache[key]=dfs(i,c);16 return cache[key];17 };18 dfs=[&](int i,int c)19 {20 if(i<0)21 return 0;22 if(c-w[i]<0)23 return cdfs(i-1,c);24 return max(cdfs(i-1,c),cdfs(i-1,c-w[i])+v[i]);25 };26 // for(int i=-1;i<(int)w.size();++i)27 // {28 // for(int j=0;j<=capacity;++j)29 // cout<<cdfs(i,j)<<' ';30 // cout<<endl;31 // }32 return cdfs(w.size()-1,capacity);33}本题需要对上述模板进行变形,变形方式如下图

python:
xxxxxxxxxx171class Solution:2 def findTargetSumWays(self, nums: List[int], target: int) -> int:3 n=len(nums)4 add=05 for k in nums:6 add+=k7 if add-target<0 or (add-target)%2==1:8 return 09 add=(add-target)//210 11 def dfs(i:int,c:int):12 if i<0:13 return 1 if c==0 else 014 if c<nums[i]:15 return dfs(i-1,c)16 return dfs(i-1,c)+dfs(i-1,c-nums[i])17 return dfs(n-1,add)C++:
xxxxxxxxxx301class Solution {2public:3 int findTargetSumWays(vector<int>& nums, int target) 4 {5 int sum=accumulate(nums.begin(),nums.end(),0);6 if(sum<target||(sum-target)%2!=0)7 return 0;8 sum=(sum-target)/2;9 //核心代码模板10 unordered_map<string,int>cache;11 function<int(int,int)>dfs;12 function<int(int,int)>cdfs=[&](int i,int c)13 {14 string key=to_string(i)+string(",")+to_string(c);15 if(cache.find(key)==cache.end())16 cache[key]=dfs(i,c);17 return cache[key];18 };19 dfs=[&](int i,int c)20 {21 if(i<0)22 return c==0?1:0;23 if(c-nums[i]<0)24 return cdfs(i-1,c);25 return cdfs(i-1,c)+cdfs(i-1,c-nums[i]);26 };27 //28 return cdfs(nums.size()-1,sum);29 }30};本题相当于v[i]=1,w[i]=nums[i]的情况
本题等价于在nums中任意取几个数相加,满足和等于
例如nums=[1,2,3,1,2],target=-1
只需在nums中任意取几个数相加,满足和等于5
arr[i][j] | 0 | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|---|
| -1 | 1 | 0 | 0 | 0 | 0 | 0 |
| 0(1) | 1 | 1 | 0 | 0 | 0 | 0 |
| 1(2) | 1 | 1 | 1 | 1 | 0 | 0 |
| 2(3) | 1 | 1 | 1 | 2 | 1 | 1 |
| 3(1) | 1 | 2 | 2 | 3 | 3 | 2 |
| 4(2) | 1 | 2 | 3 | 5 | 5 | 5 |
arr[i][j]表示只考虑nums前i个元素时,相加得到j的最多方法数
arr[i][j]=arr[i-1][j]+arr[i-1][j-nums[i]]
注意坑: s为奇数或s<0都应当返回0
C++:
xxxxxxxxxx231class Solution {2public:3 int findTargetSumWays(vector<int>& nums, int target) 4 {5 int sum=accumulate(nums.begin(),nums.end(),0);6 int add=(sum-target)/2;7 if(sum-target<0||(sum-target)%2==1)8 return 0;9 vector<vector<int>>vec(nums.size()+1);10 for(auto& vec_:vec)11 vec_.resize(add+1);12 vec[0][0]=1;13 for(int i=1;i<=nums.size();++i)14 {15 int j=0;16 for(;j<nums[i-1]&&j<=add;++j)17 vec[i][j]=vec[i-1][j];18 for(;j<=add;++j)19 vec[i][j]=vec[i-1][j]+vec[i-1][j-nums[i-1]];20 }21 return vec[nums.size()][add];22 }23};python:
xxxxxxxxxx201class Solution:2 def findTargetSumWays(self, nums: List[int], target: int) -> int:3 add=04 for k in nums:5 add+=k6 if (add-target)%2!=0 or add-target<0:7 return 08 add=(add-target)//29 size=len(nums)10 li = [0] * (size + 1)11 for k in range(size+1):12 li[k]=[0]*(add+1)13 li[0][0]=114 for i in range(1,size+1):15 for j in range(add+1):16 if j-nums[i-1]>=0:17 li[i][j]=li[i-1][j]+li[i-1][j-nums[i-1]]18 else:19 li[i][j]=li[i-1][j]20 return li[size][add]这是一个完全背包问题
举例:
xxxxxxxxxx21输入:coins = [1, 2, 3, 4, 5], amount = 72输出:3
arr[i][j]表示当前状态下所需最少硬币数
arr[i][j]=min(arr[i-1][j],arr[i][j-coins[i-1]]+1)(
i | coins | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
|---|---|---|---|---|---|---|---|---|---|
| 0 | 0 | ||||||||
| 1 | 1 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
| 2 | 2 | 0 | 1 | 1 | 2 | 2 | 3 | 3 | 4 |
| 3 | 3 | 0 | 1 | 1 | 1 | 2 | 2 | 2 | 3 |
| 4 | 4 | 0 | 1 | 1 | 1 | 1 | 2 | 2 | 2 |
| 5 | 5 | 0 | 1 | 1 | 1 | 1 | 1 | 2 | 2 |
C++:二维数组递推
xxxxxxxxxx2112class Solution {3public:4 int coinChange(vector<int>& coins, int amount) 5 {6 vector<vector<int>>vec(coins.size()+1);7 vec[0].resize(amount+1,big);8 vec[0][0]=0;9 for(int i=1;i<=coins.size();++i)10 vec[i].resize(amount+1);11 for(int i=1;i<=coins.size();++i)12 {13 int j=0;14 for(;j<coins[i-1]&&j<=amount;++j)15 vec[i][j]=vec[i-1][j];16 for(;j<=amount;++j)17 vec[i][j]=min(vec[i-1][j],vec[i][j-coins[i-1]]+1);18 }19 return vec[coins.size()][amount]==big?-1:vec[coins.size()][amount];20 }21};Python:(记忆化递归)
xxxxxxxxxx151class Solution:2 def coinChange(self, coins: List[int], amount: int) -> int:3 n=len(coins)4 5 def dfs(i,c):6 if c==0:7 return 08 if i<0 or c<0:9 return inf10 return min(dfs(i-1,c),dfs(i,c-coins[i])+1)11 ret=dfs(n-1,amount)12 if ret==inf:13 return -114 else:15 return ret优化:压缩为一维数组
C++
xxxxxxxxxx1312class Solution {3public:4 int coinChange(vector<int>& coins, int amount) 5 {6 vector<int> vec(amount+1,big);7 vec[0]=0;8 for(int& coi:coins)9 for(int i=coi;i<=amount;++i)10 vec[i]=min(vec[i],vec[i-coi]+1);11 return vec[amount]==big?-1:vec[amount];12 }13};python:
xxxxxxxxxx111class Solution:2 def coinChange(self, coins: List[int], amount: int) -> int:3 arr=[inf]*(amount+1)4 arr[0]=05 for idx,coin in enumerate(coins):6 for i in range(coin,amount+1):7 arr[i]=min(arr[i],arr[i-coin]+1)8 if arr[amount]==inf:9 return -110 else:11 return arr[amount]课后作业:
对于nums=[1,5,11,5]的测试用例
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | |
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | |
| 1 | 1 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 5 | 1 | 1 | 0 | 0 | 0 | 1 | 1 | 0 | 0 | 0 | 0 | 0 |
| 11 | 1 | 1 | 0 | 0 | 0 | 1 | 1 | 0 | 0 | 0 | 0 | 1 |
| 5 | 1 | 1 | 0 | 0 | 0 | 2 | 2 | 0 | 0 | 0 | 1 | 2 |
arr(i,c)=arr(i-1,c-num[i])+arr(i-1,c)
完成第5行时最后一列非0,可以返回True
记忆化递归
python:
xxxxxxxxxx191class Solution:2 def canPartition(self, nums: List[int]) -> bool:3 s=sum(nums)4 if s%2==1:5 return False6 s//=27 8 def dfs(i,c):9 if c==0:10 return 111 if i<0:12 return 013 if c-nums[i]<0:14 return dfs(i-1,c)15 return dfs(i-1,c-nums[i])+dfs(i-1,c)16 for k in range(len(nums)): # k从小到大进行枚举17 if(dfs(k,s)!=0):18 return True19 return False代码中k从小到大进行枚举,相当于按照nums数组由短到长枚举,很多数组只考虑前面一小段就符合条件,这样可以减少递归层级,防止超出内存限制
正常的二维数组动规:
C++:
xxxxxxxxxx361class Solution {2public:3 bool canPartition(vector<int>& nums) 4 {5 int sum=accumulate(nums.begin(),nums.end(),0);6 if(sum%2==1)7 return false;8 sum/=2;9 int m=nums.size();10 int n=sum;11 vector<vector<int>>arr(m+1);12 for(auto& ar:arr)13 ar.resize(n+1);14 int flag=0;15 for(int i=1;i<=m;++i)16 {17 for(int j=1;j<=n;++j)18 {19 if(j>=nums[i-1])20 arr[i][j]=max(arr[i-1][j],arr[i-1][j-nums[i-1]]+nums[i-1]);21 else22 arr[i][j]=arr[i-1][j];23 if(arr[i][j]==sum)24 {25 flag=1;26 goto Theend;27 }28 }29 }30 Theend:31 if(flag==1)32 return true;33 else34 return false;35 }36};Javascript:
xxxxxxxxxx311/**2 * @param {number[]} nums3 * @return {boolean}4 */5var canPartition = function(nums) 6{7 let sum=eval(nums.join('+'));8 if(sum%2!=0)9 return false;10 sum/=2;11 len=nums.length;12 let arr=new Array();13 arr[0]=new Array();14 arr[0][0]=1;15 for(let j=1;j<=sum;++j)16 arr[0][j]=0;17 for(let i=1;i<=len;++i)18 {19 arr[i]=new Array();20 for(let j=0;j<=sum;++j)21 {22 if(j-nums[i-1]<0)23 arr[i][j]=arr[i-1][j];24 else25 arr[i][j]=arr[i-1][j]+arr[i-1][j-nums[i-1]];26 }27 if(arr[i][sum]>0)28 return true;29 }30 return false;31};压缩为一维数组:
Python:使用临时数组
xxxxxxxxxx161class Solution:2 def canPartition(self, nums: List[int]) -> bool:3 s=sum(nums)4 if s%2!=0:5 return False6 s//=27 arr=[0]*(s+1)8 arr[0]=19 for idx,num in enumerate(nums):10 arr2=arr.copy() # 注意:这里要用.copy(),否则会深拷贝11 for i in range(num,s+1):12 arr2[i]+=arr[i-num]13 if arr2[s]!=0:14 return True15 arr=arr2.copy()16 return FalseC++:carl模板的倒序递推
xxxxxxxxxx221class Solution {2public:3 bool canPartition(vector<int>& nums) 4 {5 int sum=accumulate(nums.begin(),nums.end(),0);6 if(sum%2!=0)7 return false;8 sum/=2;9 cout<<sum<<endl;10 vector<int>dp(sum+1);11 for(int i=0;i<nums.size();++i)12 {13 for(int j=sum;j>=nums[i];--j)//从后往前遍历,就是0-1背包14 {15 dp[j]=max(dp[j],dp[j-nums[i]]+nums[i]); 16 }17 if(dp[sum]==sum)18 return true;19 }20 return false;21 }22};注意:本题如果用C++,只能用递推公式dp[j]=max(dp[j],dp[j-nums[i]]+nums[i]);
而不能用dp[j]+=dp[j-nums[i]],因为后者dp[i]的含义是当前枚举到的数中加和为i的所有组合总数,会溢出
分割等和子集问题的变换:
对于
可以找到一种分割子集的方法,使两个子集
有
(
最后会把石头分成两堆,重量分别为add和su-add(add<=su-add)
add的理论最大值为su//add(//是整除),只需让add从su//add开始枚举递减,直到找到一种石头组合是部分总重量为add
对应的最后一块石头的重量为su-add-add=su-2*add
python:
xxxxxxxxxx171class Solution:2 def lastStoneWeightII(self, stones: List[int]) -> int:3 su=sum(stones)4 le=len(stones)5 add=su//26 7 def dfs(i,c):8 if c==0:9 return 110 if i<0:11 return 012 if(c<stones[i]):13 return dfs(i-1,c)14 return dfs(i-1,c)+dfs(i-1,c-stones[i])15 while dfs(le-1,add)==0:16 add-=117 return abs(su-2*add)C++:
xxxxxxxxxx3212class Solution {3public:4 int lastStoneWeightII(vector<int>& stones) 5 {6 int su=accumulate(stones.begin(),stones.end(),0);7 int le=stones.size();8 int add=su/2;9 unordered_map<int,int>cache;10 function<int(int,int)>dfs;11 function<int(int,int)>cdfs=[&](int i,int c)12 {13 int key=i*mul+c;14 if(cache.find(key)==cache.end())15 cache[key]=dfs(i,c);16 return cache[key];17 };18 dfs=[&](int i,int c)19 {20 if(c==0)21 return 1;22 if(i<0)23 return 0;24 if(c-stones[i]<0)25 return cdfs(i-1,c);26 return cdfs(i-1,c)+cdfs(i-1,c-stones[i]);27 };28 while(cdfs(le-1,add)==0)29 --add;30 return su-2*add;31 }32};测试用例n=12:
arr=[1,4,9]
dfs | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 0 | |||||||||||||
| 1 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 |
| 4 | 0 | 1 | 2 | 3 | 1 | 2 | 3 | 4 | 2 | 3 | 4 | 5 | 3 |
| 9 | 0 | 1 | 2 | 3 | 1 | 2 | 3 | 4 | 2 | 1 | 2 | 3 | 3 |
dfs(i,c)=min(dfs(i-1,c),dfs(i,c-arr[i])+1)
递归会爆内存,所以只贴压缩为一维数组的递推代码
C++:
xxxxxxxxxx141class Solution {2public:3 int numSquares(int n) 4 {5 vector<int> arr(n+1);6 int g=0;7 generate(arr.begin(),arr.end(),[&](){return g++;});8 for(int i=2;i*i<=n;++i)9 for(int j=1;j<=n;++j)10 if(j-i*i>=0)11 arr[j]=min(arr[j],arr[j-i*i]+1);12 return arr[n];13 }14};python:
xxxxxxxxxx131class Solution:2 def numSquares(self, n: int) -> int:3 arr=[1]4 num=15 while arr[num-1]<=n:6 num+=17 arr.append(num**2)8 dfs=[inf]*(n+1)9 dfs[0]=010 for idx,nu in enumerate(arr):11 for i in range(nu,n+1):12 dfs[i]=min(dfs[i],dfs[i-nu]+1)13 return dfs[n]| 0 | 1 | 2 | 3 | 4 | 5 | |
|---|---|---|---|---|---|---|
| 1 | 0 | 0 | 0 | 0 | 0 | |
| 1 | 1 | 1 | 1 | 1 | 1 | 1 |
| 2 | 1 | 1 | 2 | 2 | 3 | 3 |
| 5 | 1 | 1 | 2 | 2 | 3 | 4 |
vec[i][j]=vec[i-1][j]+vec[i][j-coins[i-1]];
二维数组法
C++:
xxxxxxxxxx201class Solution {2public:3 int change(int amount, vector<int>& coins) 4 {5 vector<vector<int>>vec(coins.size()+1);6 vec[0].resize(amount+1);7 for(int i=1;i<=coins.size();++i)8 vec[i].resize(amount+1);9 vec[0][0]=1;10 for(int i=1;i<=coins.size();++i)11 {12 int j=0;13 for(;j<coins[i-1]&&j<=amount;++j)14 vec[i][j]=vec[i-1][j];15 for(;j<=amount;++j)16 vec[i][j]=vec[i-1][j]+vec[i][j-coins[i-1]];17 }18 return vec[coins.size()][amount];19 }20};(记忆化)递归法
python:
xxxxxxxxxx131class Solution:2 def change(self, amount: int, coins: List[int]) -> int: # 灵神记忆化递归模板3 n=len(coins)4 5 def dfs(i,c):6 if c==0:7 return 18 if i<0:9 return 010 if c-coins[i]<0:11 return dfs(i-1,c)12 return dfs(i-1,c)+dfs(i,c-coins[i])13 return dfs(n-1,amount)压缩为一维数组:
C++:
xxxxxxxxxx121class Solution {2public:3 int change(int amount, vector<int>& coins) 4 {5 vector<int>arr(amount+1,0);6 arr[0]=1;7 for(int& coin:coins)8 for(int i=coin;i<=amount;++i)9 arr[i]+=arr[i-coin];10 return arr[amount];11 }12};python:
xxxxxxxxxx81class Solution:2 def change(self, amount: int, coins: List[int]) -> int:3 arr=[0]*(amount+1)4 arr[0]=15 for idx,coin in enumerate(coins):6 for i in range(coin,amount+1):7 arr[i]+=arr[i-coin]8 return arr[amount]与上题几乎一样,区别使上一题求组合数,不考虑顺序,本题求排列数,考虑顺序
只需交换两个for循环的顺序
dp数组表:(nums=[1,2,3],target=4)
| 0 | 1 | 2 | 3 | 4 | |
|---|---|---|---|---|---|
| 1 | 0 | 0 | 0 | 0 | |
| 1 | 1 | 1 | 1 | 2 | 4 |
| 2 | 1 | 1 | 2 | 3 | 6 |
| 3 | 1 | 1 | 2 | 4 | 7 |
二维数组:
xxxxxxxxxx121class Solution:2 def combinationSum4(self, nums: List[int], target: int) -> int:3 4 def dfs(i,c):5 if c==0:6 return 17 if i<0:8 return 09 if c-nums[i]<0:10 return dfs(i-1,c)11 return dfs(len(nums)-1,c-nums[i])+dfs(i-1,c)12 return dfs(len(nums)-1,target)一维数组:
xxxxxxxxxx181using ll=unsigned long long;2class Solution {3public:4 int combinationSum4(vector<int>& nums, int target) 5 {6 vector<ll>dp(target+1,0);7 dp[0]=1;8 for(int j=1;j<=target;++j)9 {10 for(int i=0;i<nums.size();++i)11 {12 if(j-nums[i]>=0)13 dp[j]+=dp[j-nums[i]];14 }15 }16 return dp[target];17 }18};这是一个0-1背包问题,区别是背包容量是一个二维的情况,即要同时考虑0和1的容量
w0[i]表示str[i]含有0的个数
w1[i]表示str[i]含有1的个数
dfs(i,c,d)表示只考虑前i个字符串,0的剩余容量为c,1的剩余容量为d的情况下,字串的最大长度
dfs(i,c,d)=max{dfs(i-1,c,d),dfs(i-1,c-w0[i],d-w1[i])+1}
方法1:灵神模板记忆化递归
python:
xxxxxxxxxx161class Solution:2 def findMaxForm(self, strs: List[str], m: int, n: int) -> int:3 le=len(strs)4 w0=[0]*le5 w1=[0]*le6 for idx,s in enumerate(strs):7 w0[idx]=s.count("0")8 w1[idx]=s.count("1")9 10 def dfs(i,c,d):11 if i<0:12 return 013 if c<w0[i] or d<w1[i]:14 return dfs(i-1,c,d)15 return max(dfs(i-1,c,d),dfs(i-1,c-w0[i],d-w1[i])+1)16 return dfs(le-1,m,n)C++:
xxxxxxxxxx34123class Solution {4public:5 int findMaxForm(vector<string>& strs, int m, int n) 6 {7 int le=strs.size();8 vector<int>w0=vector<int>(le);9 vector<int>w1=vector<int>(le);10 for(int i=0;i<strs.size();++i)11 {12 w0[i]=count(strs[i].begin(),strs[i].end(),'0');13 w1[i]=count(strs[i].begin(),strs[i].end(),'1');14 }15 unordered_map<int,int>cache;16 function<int(int,int,int)>dfs;17 function<int(int,int,int)>cdfs=[&](int i,int n0,int n1)18 {19 int key=i*m1+n0*m2+n1;20 if(cache.find(key)==cache.end())21 cache[key]=dfs(i,n0,n1);22 return cache[key];23 };24 dfs=[&](int i,int n0,int n1)25 {26 if(i<0)27 return 0;28 if(n0-w0[i]<0||n1-w1[i]<0)29 return cdfs(i-1,n0,n1);30 return max(cdfs(i-1,n0,n1),cdfs(i-1,n0-w0[i],n1-w1[i])+1);31 };32 return cdfs(le-1,m,n);33 }34};方法2:三维数组动规
C++:
xxxxxxxxxx451class Solution {2public:3 int findMaxForm(vector<string>& strs, int m, int n) 4 {5 int len=strs.size();6 vector<int>w0(len);7 vector<int>w1(len);8 for(int i=0;i<len;++i)9 {10 w0[i]=count(strs[i].begin(),strs[i].end(),'0');11 w1[i]=count(strs[i].begin(),strs[i].end(),'1');12 }13 vector<vector<vector<int>>> vec(len);14 for(auto& vec_1:vec)15 {16 vec_1.resize(m+1);17 for(auto& vec_2:vec_1)18 vec_2.resize(n+1);19 }20 for(int i=0;i<len;++i)21 {22 for(int j=0;j<=m;++j)23 {24 for(int k=0;k<=n;++k)25 {26 if(i==0)27 {28 if(j<w0[i]||k<w1[i])29 vec[i][j][k]=0;30 else 31 vec[i][j][k]=1;32 continue;33 }34 if(j-w0[i]<0||k-w1[i]<0)35 {36 vec[i][j][k]=vec[i-1][j][k];37 continue;38 }39 vec[i][j][k]=max(vec[i-1][j][k],vec[i-1][j-w0[i]][k-w1[i]]+1);40 }41 }42 }43 return vec[len-1][m][n];44 }45};xxxxxxxxxx271class Solution:2 def profitableSchemes(self, n: int, minProfit: int, group: List[int], profit: List[int]) -> int:3 m=10**9+74 le=len(group)5 # 首先计算符合人数要求的所有方案6 7 def dp1(i,num):8 if i<0:9 return 110 if num-group[i]<0:11 return dp1(i-1,num)12 return (dp1(i-1,num)+dp1(i-1,num-group[i]))%m13 ans1=dp1(le-1,n)14 # 然后计算利润小于minProfit的方案15 16 def dp2(i,g,p):17 if i==-1:18 return 1 if p==0 else 019 if g-group[i]<0 or p-profit[i]<0:20 return dp2(i-1,g,p)%m21 return (dp2(i-1,g-group[i],p-profit[i])+dp2(i-1,g,p))%m22 maxprofit=sum(profit)23 ans2=024 for i in range(minProfit):25 ans2+=dp2(len(group)-1,n,i)26 ans2%=m27 return (ans1+m-ans2)%m最长公共子序列 编辑距离【基础算法精讲 19】 (参考视频)

可以得到递推式:

可以证明,简化后结果为
python:
xxxxxxxxxx141class Solution:2 def longestCommonSubsequence(self, text1: str, text2: str) -> int:3 m=len(text1)4 n=len(text2)5 arr=[[]]*(m+1)6 for idx,arr_ in enumerate(arr):7 arr[idx]=[0]*(n+1)8 for i in range(1,m+1):9 for j in range(1,n+1):10 if text1[i-1]==text2[j-1]:11 arr[i][j]=arr[i-1][j-1]+112 else:13 arr[i][j]=max(arr[i-1][j],arr[i][j-1])14 return arr[m][n]| dp(i,j) | r | o | s | |
|---|---|---|---|---|
| 0 | 1 | 2 | 3 | |
| h | 1 | 1 | 2 | 3 |
| o | 2 | 2 | 1 | 2 |
| r | 3 | 2 | 2 | 2 |
| s | 4 | 3 | 3 | 2 |
| e | 5 | 4 | 4 | 3 |
xxxxxxxxxx141class Solution:2 def minDistance(self, word1: str, word2: str) -> int:3 4 def dp(i,j):5 if i==-1 and j==-1:6 return 07 if i==-1:8 return dp(i,j-1)+19 if j==-1:10 return dp(i-1,j)+111 if word1[i]==word2[j]:12 return dp(i-1,j-1)13 return min(dp(i-1,j),dp(i,j-1),dp(i-1,j-1))+114 return dp(len(word1)-1,len(word2)-1)课后作业:
xxxxxxxxxx151class Solution:2 def minimumDeleteSum(self, s1: str, s2: str) -> int:3 4 def dp(i,j):5 if i<0 or j<0:6 return 07 if s1[i]!=s2[j]:8 return max(dp(i-1,j),dp(i,j-1))9 return dp(i-1,j-1)+ord(s1[i])10 add=011 for ch in s1:12 add+=ord(ch)13 for ch in s2:14 add+=ord(ch)15 return add-2*dp(len(s1)-1,len(s2)-1)| 3 | 0 | -6 | ||
|---|---|---|---|---|
| 0 | 0 | 0 | 0 | |
| 2 | 0 | 6 | 6 | 6 |
| 1 | 0 | 6 | 6 | 6 |
| -2 | 0 | 6 | 6 | 18 |
| 5 | 0 | 15 | 15 | 18 |
xxxxxxxxxx201class Solution:2 def maxDotProduct(self, nums1: List[int], nums2: List[int]) -> int:3 4 def dp(i,j): # 记忆化递归5 if i<0 or j<0:6 return 07 return max(dp(i-1,j-1)+nums1[i]*nums2[j],dp(i-1,j),dp(i,j-1))8 ret=dp(len(nums1)-1,len(nums2)-1)9 if ret==0: # ret==0可能是因为答案为负数,此时需要分别找出两个数组中绝对值最小的元素,并相乘10 min1=inf11 for n in nums1:12 if abs(n)<abs(min1):13 min1=n14 min2=inf15 for n in nums2:16 if abs(n)<abs(min2):17 min2=n18 return min1*min219 else:20 return ret三维dp
xxxxxxxxxx101class Solution:2 def isInterleave(self, s1: str, s2: str, s3: str) -> bool:3 4 def dp(i,j,k):5 if i==-1 and j==-1 and k==-1:6 return True7 elif k==-1:8 return False9 return i!=-1 and dp(i-1,j,k-1) and s1[i]==s3[k] or j!=-1 and dp(i,j-1,k-1) and s2[j]==s3[k]10 return dp(len(s1)-1,len(s2)-1,len(s3)-1)C++:
xxxxxxxxxx211class Solution {2public:3 vector<int> dailyTemperatures(vector<int>& temperatures) 4 {5 vector<int> vec=temperatures;6 int n=vec.size();7 stack<pair<int,int>> sta;8 vector<int>ret(n);9 for(int i=n-1;i>=0;--i)10 {11 while(!sta.empty()&&sta.top().first<=vec[i])12 sta.pop();13 if(sta.empty())14 ret[i]=0;15 else16 ret[i]=sta.top().second-i;17 sta.push(make_pair(vec[i],i));18 }19 return ret;20 }21};python:
xxxxxxxxxx101class Solution:2 def dailyTemperatures(self, temperatures: List[int]) -> List[int]:3 stack=[[inf,-1]] # 单调栈,其中元素必须递减4 ret=[0]*len(temperatures)5 for idx,num in enumerate(temperatures):6 while stack[len(stack)-1][0]<num:7 ret[stack[len(stack)-1][1]]=idx-stack[len(stack)-1][1]8 stack.pop(len(stack)-1)9 stack.append([num,idx])10 return ret原理和上一题一样,时间复杂度为O(nums1.length + nums2.length)
xxxxxxxxxx291class Solution {2public:3 vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) 4 {5 unordered_map<int,int> hash;6 for(int i=0;i<nums2.size();++i)7 {8 hash[nums2[i]]=i;9 }10 stack<int> sta;11 vector<int>ans(nums2.size());12 for(int i=nums2.size()-1;i>=0;--i)13 {14 while(!sta.empty()&&sta.top()<=nums2[i])15 sta.pop();16 if(sta.empty())17 ans[i]=-1;18 else19 ans[i]=sta.top();20 sta.push(nums2[i]);21 }22 vector<int> ret(nums1.size());23 for(int i=0;i<nums1.size();++i)24 {25 ret[i]=ans[hash[nums1[i]]];26 }27 return ret;28 }29};